标准的最大流. 注意有重边. 重复边直接累加.

/**//*
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
小阮 阅读(215)
评论(0) 编辑 收藏 引用 所属分类:
USACO