/**//*
sap+gap优化+当前弧优化, 采用邻接表+反向弧指针
时间复杂度:O(mn^2)
*/
#include<iostream>
using namespace std;
const int maxnode = 1024;
const int inf = 0x7fffffff;
struct edge
{
int ver;
int cap;
edge *next; //next arc
edge *rev; //reverse arc
edge() {}
edge(int Vertex, int Capacity, edge *Next):ver(Vertex), cap(Capacity), next(Next) {}
void* operator new(size_t, void* p) {return p;}
}*Net[maxnode];
int dis[maxnode], num[maxnode], src, des, m, n;
int min(int a, int b)
{
return a<b? a:b;
}
void rev_bfs()
{
for(int i=1; i<=n; i++)
{
dis[i] = maxnode;
num[i] = 0;
}
int q[maxnode], head = 0,tail = 0;
q[tail++] = des;
dis[des] = 0;
num[0] = 1;
while(head != tail)
{
int v = q[head++];
for(edge *e = Net[v]; e; e = e->next)
{
if(dis[e->ver] == maxnode && e->rev->cap > 0)
{
dis[e->ver] = dis[v] + 1;
num[dis[e->ver]]++;
q[tail++] = e->ver;
}
}
}
}
int maxflow()
{
int u, totalflow = 0;
edge *curedge[maxnode], *revpath[maxnode];
for(int i=1; i<=n; i++) curedge[i] = Net[i];
u = src;
while(dis[src] < n)
{
edge *e;
for(e = curedge[u]; e; e = e->next)
if(e->cap > 0 && dis[u] == dis[e->ver] + 1) break;
if(e)
{
curedge[u] = e;
revpath[e->ver] = e->rev;
u = e->ver;
if(u == des)
{
int augflow = inf, i;
for(i = src; i != des; i = curedge[i]->ver)
augflow = min(augflow, curedge[i]->cap);
for(i = src; i != des; i = curedge[i]->ver)
{
curedge[i]->cap -= augflow;
curedge[i]->rev->cap +=augflow;
}
totalflow += augflow;
u = src;
}
}
else
{
if(0 == (--num[dis[u]])) break;
curedge[u] = Net[u];
int mindist = n;
for(edge *te = Net[u]; te; te = te->next)
if(te->cap > 0) mindist = min(mindist, dis[te->ver]);
dis[u]=mindist + 1;
++num[dis[u]];
if(u != src)
u = revpath[u]->ver;
}
}
return totalflow;
}
int main()
{
int u, v, w;
while(scanf("%d%d", &m, &n) != EOF)
{
edge *Te = new edge[2*m];
edge *Pe = Te;
src = 1;
des = n;
memset(Net,0,sizeof(Net));
while(m--)
{
scanf("%d%d%d", &u, &v, &w);
//if(u==v) continue;
Net[u] = new((void*)Pe++) edge(v, w, Net[u]);
Net[v] = new((void*)Pe++) edge(u, 0, Net[v]);
Net[u]->rev = Net[v];
Net[v]->rev = Net[u];
}
rev_bfs();
printf("%d\n",maxflow());
delete [] Te;
}
return 0;
}posted on 2011-05-10 13:17
wuxu 阅读(730)
评论(0) 编辑 收藏 引用 所属分类:
图论