标准的最大流. 注意有重边. 重复边直接累加.
/**//*
ID: lorelei3
TASK: ditch
LANG: C++
*/
#include <fstream>
#include <queue>
#include <memory.h>
using namespace std;
const int INF = 0x7FFFFFF;
const int MAXN = 205;
int s,t,n;
long long c[MAXN][MAXN], pre[MAXN], delta[MAXN];
bool bfs(int s, int t)
{
int i;
queue<int> Q;
memset(pre, 0, sizeof(pre));
memset(delta, 0, sizeof(delta));
delta[s] = INF;
Q.push(s);
while(!Q.empty()){
int cur = Q.front();
Q.pop();
for(i=1; i<=n; ++i){
if(delta[i]==0 && c[cur][i]>0){
delta[i] = delta[cur]<c[cur][i] ? delta[cur] : c[cur][i];
pre[i] = cur;
Q.push(i);
}
}
}
if(delta[t]==0)
return false;
return true;
}
int edmonds_karp(int s, int t){
int i, ans=0;
while(bfs(s,t)){
for(i=t; i!=s; i=pre[i]){
c[pre[i]][i] -= delta[t];
c[i][pre[i]] += delta[t];
}
ans += delta[t];
}
return ans;
}
int main(){
int k,i,j,v;
ifstream fin("ditch.in");
ofstream fout("ditch.out");
fin>>k>>n;
s=1; t=n;
while(k--){
fin>>i>>j>>v;
c[i][j]+=v;
}
fout<<edmonds_karp(s,t)<<endl;
return 0;
}posted on 2011-01-24 22:42
小阮 阅读(210)
评论(0) 编辑 收藏 引用 所属分类:
USACO