/**//*
dinic算法,邻接矩正,O(mn^2)
*/
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxnode=205;
const int inf=0x7fffffff;
int level[maxnode];
int r[maxnode][maxnode];
int curedge[maxnode];//保存每个顶点引出的当前边
bool vis[maxnode];
int stk[maxnode]; //栈
int top; //栈顶
int m,n,src,sin;
int min(int a,int b)
{
return a<b? a:b;
}
void bfs_level()
{
memset(level,-1,sizeof(level));
queue<int> q;
level[src]=0;
q.push(src);
while(!q.empty())
{
int k=q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(level[i]==-1&&r[k][i]>0)
{
level[i]=level[k]+1;
q.push(i);
}
}
}
}
int dfs_maxflow()
{
for(int k=1;k<=n;k++)
{
curedge[k]=1;
vis[k]=false;
}
int flow=0;
top=0;
stk[top]=src;
int curptr;
while(top>=0)
{
if(stk[top]==sin)
{
int mint=inf, j;
for(j=top;j>0;j--)
mint=min(mint,r[stk[j-1]][stk[j]]);
for(j=top;j>0;j--)
{
r[stk[j-1]][stk[j]]-=mint;
r[stk[j]][stk[j-1]]+=mint;
if(r[stk[j-1]][stk[j]]==0) curptr=j;
}
top=curptr-1;
flow+=mint;
}
else
{
int i;
bool flag=false;
for(i=curedge[stk[top]];i<=n;i++)
{
curedge[stk[top]]++;
if(r[stk[top]][i]>0&&!vis[i]&&level[stk[top]]+1==level[i])
{
flag=true;
stk[++top]=i;
break;
}
}
if(!flag)
{
vis[stk[top]]=true;
top--;
}
}
}
return flow;
}
int dinic()
{
int maxflow=0, t;
while(1)
{
bfs_level();
if(level[sin]==-1) return maxflow;
t=dfs_maxflow();
if(!t) return maxflow;
maxflow+=t;
}
return maxflow;
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(r,0,sizeof(r));
src=1; /**/////!!
sin=n;
int u,v,w;
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
r[u][v]+=w;
}
printf("%d\n",dinic());
}
return 0;
}
posted on 2011-05-10 13:05
wuxu 阅读(333)
评论(0) 编辑 收藏 引用 所属分类:
图论