题目链接：http://poj.org/problem?id=1273

很经典的最大流问题，用此总结dinic模板

dinic比E-K多了个DFS，只要明白什么是把图分层了，就不难理解了。BFS找增广路的同时把图分层，相当于记录了多条增广路，可以让每次dinic能处理尽量多的增广路。

模板：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MAX 65535 struct node { int e; int w; int fro; }eg[400]; int head[400]; //正儿八经的前向星 using namespace std; int cont; void add(int s,int e,int w) //加边 { eg[cont].e = e; //前向弧 eg[cont].w = w; eg[cont].fro = head[s]; head[s] = cont++; eg[cont].e = s; //反向弧 eg[cont].w = 0; eg[cont].fro = head[e]; head[e] = cont++; return ; } int dis[400]; int BFS(int s,int e) //BFS找增光路 并且分层次 { int now,tmp; memset(dis,-1,sizeof (dis)); queue
       
         que; que.push(s); dis[s] = 0; while (!que.empty()) { now = que.front(); que.pop(); for (int i = head[now];i != -1;i = eg[i].fro) { int v = eg[i].e; if (dis[v] == -1 && eg[i].w > 0) { dis[v] = dis[now] + 1; //分层 que.push(v); } } } if (dis[e] != -1) return 1; return 0; } int dinic(int s,int e,int t) { if (s == e) return t; int tmp = t; for (int i = head[s];i != -1;i = eg[i].fro) { int v = eg[i].e; if(dis[v] == dis[s] + 1 && eg[i].w > 0) { int imin = dinic(v,e,min(t,eg[i].w)); //递归找最小容量，其实就是个DFS eg[i].w -= imin; eg[i ^ 1].w += imin; t -= imin; } } return tmp - t; } int main() { int n,m; while (~scanf ("%d%d",&n,&m)) { int i; cont = 0; memset(head,-1,sizeof (head)); for (i = 0;i < n;i++) { int a,b,c; scanf ("%d%d%d",&a,&b,&c); add(a,b,c); } int ans = 0; while (BFS(1,m)) ans += dinic(1,m,MAX); printf ("%d\n",ans); } return 0; }