peltorator

Алгоритм Диница

Feb 22nd, 2017
172
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. const ll MAXN = 200001;
  3.  
  4. vector<ll> num[MAXN], g[MAXN], c[MAXN], f[MAXN], lvl, p, used, ans, rev[MAXN];
  5.  
  6. ll n;
  7.  
  8. bool bfs()
  9. {
  10.     lvl[1] = 0;
  11.     queue<ll> q;
  12.     q.push(1);
  13.     while (q.size())
  14.     {
  15.         ll v = q.front();
  16.         q.pop();
  17.         for (ll i = 0; i < g[v].size(); i++)
  18.         {
  19.             ll u = g[v][i];
  20.             if (lvl[u] == -1 && c[v][i] > f[v][i])
  21.             {
  22.                 lvl[u] = lvl[v] + 1;
  23.                 q.push(u);
  24.             }
  25.         }
  26.     }
  27.     return lvl[n] != -1;
  28. }
  29.  
  30. ll dfs(ll v, ll flow)
  31. {
  32.     if (v == n || flow == 0)
  33.         return flow;
  34.     for (ll i = 0; i < g[v].size(); i++)
  35.     {
  36.         ll u = g[v][i];
  37.         if (lvl[u] == lvl[v] + 1)
  38.         {
  39.             ll cur = dfs(u, min(flow, c[v][i] - f[v][i]));
  40.             f[v][i] += cur;
  41.             f[u][rev[v][i]] -= cur;
  42.             if (cur)
  43.                 return cur;
  44.         }
  45.     }
  46.     return 0;
  47. }
  48.  
  49. void dfs1(ll v)
  50. {
  51.     used[v] = 1;
  52.     for (ll i = 0; i < g[v].size(); i++)
  53.         if (!used[g[v][i]] && c[v][i] > f[v][i])
  54.             dfs1(g[v][i]);
  55. }
  56.  
  57. int main()
  58. {
  59.     ll m;
  60.     cin >> n >> m;
  61.     for (ll i = 1; i <= m; i++)
  62.     {
  63.         ll k, l, w;
  64.         cin >> k >> l >> w;
  65.         g[k].push_back(l);
  66.         f[k].push_back(0);
  67.         num[k].push_back(i);
  68.         c[k].push_back(0);
  69.         rev[k].push_back(g[l].size());
  70.  
  71.         g[l].push_back(k);
  72.         f[l].push_back(0);
  73.         num[l].push_back(i);
  74.         c[l].push_back(0);
  75.         rev[l].push_back(g[k].size() - 1);
  76.     }
  77.     p.assign(n + 1, 0);
  78.     while (true)
  79.     {
  80.         lvl.assign(n + 1, -1);
  81.         if (!bfs())
  82.             break;
  83.         dfs(1, 1e9);
  84.     }
  85.     used.assign(n + 1, 0);
  86.     dfs1(1);
  87.     ll vel = 0;
  88.     for (ll v = 1; v <= n; v++)
  89.         if (used[v])
  90.             for (ll j = 0; j < g[v].size(); j++)
  91.                 if (!used[g[v][j]])
  92.                     ans.push_back(num[v][j]), vel += c[v][j];
  93.     sort(ans.begin(), ans.end());
  94.     cout << ans.size() << " " << vel << endl;
  95.     for (ll i : ans)
  96.         cout << i << " ";
  97.     return 0;
  98. }
RAW Paste Data