POJ 1293 网络流 第一题

完全的模板，做多了就好了吧

反向流量真的很有意思，有这样一种说法比较容易理解。”正向是+，反向就是-，其实是等价的。因为每次找到的增广路不一定是最优解里面的，所以再进行后面的操作的时候要重新选择，而反向流量就类似于回溯的作用。相当于撤销了刚才选择的u->v的流“。

 #include <iostream>

 #include <cstdio>

 #include <queue>

 #include <algorithm>

 #define INF 999999999

 //#define OPEN_FILE

 using namespace std;

 const int MAXN = , MAXM = , MAXL = ;

 struct Node

 {

     int id, v;

 };

 int cap[MAXM][MAXM], flow[MAXM][MAXM], a[MAXM], f[MAXM];

 int ans, n, m;

 void ek_bfs()

 {

     int u, v, s, t;

     s = ;

     t = m;

     ans = ;

     queue<int> d;

     while (){

         memset(a, , sizeof(a));

         a[s] = INF;

         d.push(s);

         while (!d.empty()){

             u = d.front();

             d.pop();

             for (v = s; v <= t; v++){

                 if (a[v] || cap[u][v] <= flow[u][v]) continue;

                 f[v] = u;

                 d.push(v);

                 a[v] = min(a[u], cap[u][v] - flow[u][v]);

             }

         }

         if (a[t] == ) break;

         for (u = t; u != s; u = f[u]){

             flow[f[u]][u] += a[t];

             flow[u][f[u]] -= a[t];

         }

         ans += a[t];

     }

 }

 int main()

 {

 #ifdef OPEN_FILE

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w", stdout);

 #endif // OPEN_FILE

     int i, x, y, z;

     while (~scanf("%d%d", &n, &m)){

         memset(flow, , sizeof(flow));

         memset(cap, , sizeof(cap));

         for (i = ; i <= n; i++){

             scanf("%d%d%d", &x, &y, &z);

             cap[x][y] += z;

         }

         ek_bfs();

         printf("%d\n", ans);

     }

 }