Untitled

Автор: Ivan, 1 Год назад, написана на языке C++, просмотрена 172 раз(а).
URL https://pastie.ru/view/c691ee80 Встраивание на сайт
Скачать заметку или Посмостреть исходник Test1
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long LL;
  8.  
  9. const int MAXN = 510;
  10. const int MAXM = 20010;
  11. const int INF = (int) 2e9;
  12.  
  13. vector<int> g[MAXN];
  14. int fr[MAXM], to[MAXM], cap[MAXM], f[MAXM];
  15. int ptr[MAXN], level[MAXN];
  16. int edges = 0;
  17. int q[MAXN];
  18.  
  19. void add_edge(int fr_, int to_, int cap_) {
  20.   fr[edges] = fr_;
  21.   to[edges] = to_;
  22.   cap[edges] = cap_;
  23.   f[edges] = 0;
  24.   g[fr_].push_back(edges);
  25.   ++edges;
  26.  
  27.   fr[edges] = to_;
  28.   to[edges] = fr_;
  29.   cap[edges] = 0;
  30.   f[edges] = 0;
  31.   g[to_].push_back(edges);
  32.   ++edges;
  33. }
  34.  
  35. bool bfs(int n) {
  36.   memset(level, -1, sizeof(level));
  37.   int qpos = 1;
  38.   int ql = 0;
  39.   q[0] = 0;
  40.   level[0] = 0;
  41.   while (ql < qpos) {
  42.     int v = q[ql];
  43.     for (int e : g[v]) {
  44.       int tov = to[e];
  45.       if (level[tov] == -1 && cap[e] - f[e] > 0) {
  46.         level[tov] = level[v] + 1;
  47.         q[qpos++] = tov;
  48.       }
  49.     }
  50.     ++ql;
  51.   }
  52.   return (level[n - 1] != -1);
  53. }
  54.  
  55. int dfs(int v, int ed, int flow) {
  56.   if (v == ed) {
  57.     return flow;
  58.   }
  59.  
  60.   int sz = g[v].size();
  61.   for (; ptr[v] < sz; ++ptr[v]) {
  62.     int e = g[v][ptr[v]];
  63.     if (level[v] + 1 == level[to[e]] && cap[e] > f[e]) {
  64.       int cflow = dfs(to[e], ed, min(flow, cap[e] - f[e]));
  65.       if (cflow) {
  66.         f[e] += cflow;
  67.         f[e ^ 1] -= cflow;
  68.         return cflow;
  69.       }
  70.     }
  71.   }
  72.   return 0;
  73. }
  74.  
  75. LL max_flow(int n) {
  76.   LL flow = 0;
  77.   while (bfs(n)) {
  78.     memset(ptr, 0, sizeof(ptr));
  79.     int cflow = dfs(0, n - 1, INF);
  80.     while (cflow) {
  81.       flow += cflow;
  82.       cflow = dfs(0, n - 1, INF);
  83.     }
  84.   }
  85.   return flow;
  86. }
  87.  
  88. int main() {
  89.   ios_base::sync_with_stdio(false);
  90.   int n, m;
  91.   cin >> n >> m;
  92.   for (int i = 0; i < m; ++i) {
  93.     int a, b, c;
  94.     cin >> a >> b >> c;
  95.     --a, --b;
  96.     add_edge(a, b, c);
  97.   }
  98.  
  99.   cout << max_flow(n) << endl;
  100.   return 0;
  101. }
  102.  
Ответить: "Untitled"

Здесь Вы можете ответить на заметку выше