/* ***********************************************
Author :guanjun
Created Time :2015/6/16 20:39:26
File Name :7.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 1<<30
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int cap[20][20];
int flow[20][20];
int a[20];//最小残量
int p[20];
int f;
void Ek(int n,int s,int t){
queue<int>q;
memset(flow,0,sizeof flow);
f=0;//总流量
for(;;){
memset(a,0,sizeof a);
a[s]=INF;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
for(int v=1;v<=n;v++)if(!a[v]&&cap[u][v]>flow[u][v]){ //找到新的结点v
p[v]=u;q.push(v); //记录v的父节点 并入fifo队列
a[v]=min(a[u],cap[u][v]-flow[u][v]); //s-v路径上的最小残量
}
}
if(a[t]==0)break; //找不到 则当前流已经是最大流
for(int u=t;u!=s;u=p[u]){ //从汇点往回走
flow[p[u]][u]+=a[t]; //更新正向流量
flow[u][p[u]]-=a[t]; //更新反向流量
}
f+=a[t]; //更新从s流出的总流量
}
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int n,m;
int s,t;
int cnt=0;
int T;
cin>>T;
while(T--){
cin>>n>>m;
int x,y,z;
cle(cap);
for(int i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&z);
cap[x][y]+=z;//重编的时候+=z
}
f=0;
Ek(n,1,n);
printf("Case %d: %d\n",++cnt,f);
}
return 0;
}
2015年06月17日
速度EK模板
http://acm.hdu.edu.cn/showproblem.php?pid=3549