POJ 1273(EK)

题目大概意思是，有N条水沟和M个水池,问从第一个水池到最后一个水池在同一时间内能够流过多少水
第一行有两个整数N,M
接下来N行,每行有3个整数,a,b,c,代表从a到b能够流c单位的水
超级模板题,一个有向图,源点为1,汇点为M,套最大流模板就行了

我就通过这水题理解EK的...

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<queue>

 #include<climits>

 using namespace std;

 #define N 210

 #define clr(a,b) memset(a,b,sizeof(a))

 int cap[N][N];///容量

 int n,m;

 int a,b,c;

 int EK(int s,int t)///s代表源点，t代表汇点

 {

     queue<int> q;

     int flow[N][N];///流量

     int low[N];///low[v]表示s-v的最小残量

     int pre[N];///用于BFS寻找父亲节点

     int u,v;

     int maxflow = ;///最大流

     clr(flow,);///初始时残量网络为0

     while()

     {

         q.push(s);///把源点压入队列中

         clr(low,);

         low[s] = INT_MAX;

         while(!q.empty())

         {

             u = q.front();

             q.pop();

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

             {

                 if(!low[v] && cap[u][v] > flow[u][v])///找到新节点v

                 {

                     q.push(v);

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

                     pre[v] = u;

                 }

             }

         }

         if(low[t] == ) break;///找不到，则当前流已经是最大

         for(u = t; u != s; u = pre[u])

         {

             flow[pre[u]][u] += low[t];

             flow[u][pre[u]] -= low[t];

         }

         maxflow += low[t];

     }

     return maxflow;

 }

 int main()

 {

     int ans;

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

     {

         clr(cap,);

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

         {

             scanf("%d%d%d",&a,&b,&c);

             cap[a][b] += c;

         }

         ans = EK(,m);

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

     }

     return ;

 }