poj 1273最大流dinic算法模板

#include<stdio.h>

#include<string.h>

#define N 300

#define inf 0x7fffffff

#include<queue>

using namespace std;

struct node {

int u,v,w,next;

}bian[N*4];

int head[N],yong,d[N],s,t;

void addedge(int u,int v,int w) {

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

int Min(int a,int b) {

return a>b?b:a;

}

int bfs() {

int i,cur,v;

queue<int>q;

memset(d,0,sizeof(d));

q.push(s);

d[s]=1;

while(!q.empty()) {

cur=q.front();

q.pop();

for(i=head[cur];i!=-1;i=bian[i].next) {

v=bian[i].v;

if(bian[i].w&&!d[v]) {

d[v]=d[cur]+1;

if(v==t)

return 1;

q.push(v);

}

}

}

return 0;

}

int dfs(int u,int limit) {

int cost=0,v,i,flow;

if(u==t)

return limit;

for(i=head[u];i!=-1;i=bian[i].next) {

v=bian[i].v;

if(bian[i].w&&d[v]==d[u]+1) {

flow=dfs(v,Min(limit-cost,bian[i].w));

if(flow>0) {//

bian[i].w-=flow;

bian[i^1].w+=flow;

cost+=flow;

if(limit==cost)//如果已经搜到了满流就跳出

break;

}

else

d[v]=-1;//如果流量等于零，再遇到这个点就进行不下去了

}

}

return cost;

}

int dinic() {

int sum=0;

while(bfs())//建层次图

sum+=dfs(s,inf);//多次dfs搜索s-t增光路求可行流

return sum;

}

int main(){

int m,i,j,k,n;

while(scanf("%d%d",&m,&n)!=EOF) {

yong=0;

memset(head,-1,sizeof(head));

s=1;t=n;

while(m--){

scanf("%d%d%d",&i,&j,&k);

addedge(i,j,k);//建边

addedge(j,i,0);//建反向边

}

printf("%d\n",dinic());

}

return 0;

}

巴特西

poj 1273最大流dinic算法模板

最新文章

热门文章