Posted on 2012-05-01 01:05
lenohoo 閱讀(87)
評論(0) 編輯 收藏 引用
relabel_to_front
#include<cstdio>
#include<cstring>
#include<iostream>
#include<list>
using namespace std;
const int INF = 1000001;
const int N = 101;
int C[N][N],F[N][N];
int E[N],H[N];
int n,m,ans;
bool changed;
void push(int u,int v,int delta)
{
F[u][v]+=delta;F[v][u]-=delta;
E[u]-=delta;E[v]+=delta;
}
void relable(int u)
{
H[u]++;
}
void discharge(int u)
{
if(E[u]==0) { changed=false;return; }
changed=true;
for(int v=2;v<=n;v++){
if(u == v) continue;
if(H[u]>H[v] && F[u][v]<C[u][v])
push(u,v,min(E[u],C[u][v]-F[u][v]));
}
if(E[u]==0) { changed=false;return; }
}
void relable_to_front()
{
memset(E,0,sizeof(E));
memset(H,0,sizeof(H));
H[1]=n;E[1]=INF;
for(int v=2;v<=n;v++){
if(F[1][v] < C[1][v]){
push(1,v,C[1][v]);
if(v!=n) H[v]++;
}
}
list<int> L;
for(int i=2;i<n;i++) L.push_back(i);
list<int> :: iterator it=L.begin();
while(it!=L.end())
{
discharge(*it);
if(changed){
L.push_front(*it);L.erase(it);
it=L.begin();
}
else it++;
}
}
void init()
{
int u,v,w;
memset(C,0,sizeof(E));
memset(F,0,sizeof(F));
cin>>m>>n;
for(int i=0;i<m;i++){
cin>>u>>v>>w;
C[u][v]+=w;
}
}
int main()
{
while(1){
init();
relable_to_front();
cout<<E[n]<<endl;
}
}