UESTC_传输数据 2015 UESTC Training for Graph Theory<Problem F>

F - 传输数据

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

机房里面有m台电脑，n台网线，每条网线都每秒中最多传送的数据量，现在需要你计算从标号为1的电脑传送数据到编号为m的电脑，问一秒内最多传送多少数据?

Input

第1行: 两个用空格分开的整数N(0≤N≤200)和 M(2≤M≤200)。N网线的数量，M是电脑的数量。

第二行到第N+1行: 每行有三个整数，Si，Ei 和 Ci。Si 和 Ei (1≤Si,Ei≤M) 指明电脑编号，数据从 Si 流向 Ei。Ci(0≤Ci≤10,000,000)是这条网线的最大容量。

Output

输出一个整数，即排水的最大流量。

Sample input and output

Sample Input	Sample Output
5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10	50

解题报告:

解题报告:

 这是一道赤裸裸的最大流题目，我使用了ek算法，虽然效率不高，但是本题数据规模不大，所以直接用ek算法解决.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 200 + 10;
int c[maxn][maxn]; //流量限制
int f[maxn][maxn]; //目前流量
int p[maxn];       //残余流量
int pre[maxn];     //路径记录 
const int inf = 0x5fffffff;
int n,m;
queue<int>q;

int ek(int st,int ed)
{
   int flow = 0;
   while(1)
    {
        memset(p,0,sizeof(p));
        p[st] = inf,pre[st] = 0;
        q.push(st);
        while(!q.empty())
         {
              int x = q.front();q.pop();
              for(int i = 1 ; i <= m ; ++ i)
               if (!p[i] && f[x][i] < c[x][i]) //允许增广 
                {
                      q.push(i);
                      pre[i] = x; //路径记录
                  p[i] = min(c[x][i] - f[x][i] , p[x]); 
               }
         }
        if (!p[ed]) // 增广路搜寻完毕，无可增加的流量 
         break;
        int cur = ed;
        while(cur)
         {
             f[pre[cur]][cur] += p[ed];
             f[cur][pre[cur]] -= p[ed];
             cur = pre[cur];
         }
        flow += p[ed];
    }
   return flow;
}



int main(int argc,char *argv[])
{
  memset(c,0,sizeof(c));
  memset(f,0,sizeof(f));
  scanf("%d%d",&n,&m);
  while(n--)
   {
         int u,v,w;
         scanf("%d%d%d",&u,&v,&w);
         c[u][v] += w;
   }
  printf("%d
",ek(1,m));
  return 0;
}