第一个版本EK
#include<stdio.h> #define MAX 0x3f3f3f3f #define min(x,y) ((x<y)?(x):(y)) int map[300][300]; int dis[300]; int q[2000],h,r; int N,M,ANS; int BFS(void) { int i,j; memset(dis,0xff,sizeof(dis)); dis[1]=0; h=0;r=1; q[1]=1; while(h<r) { j=q[++h]; for(i=1;i<=N;i++) { if(dis[i]<0&&map[j][i]>0) { dis[i]=dis[j]+1; q[++r]=i; } } } if(dis[N]>0) return 1; else return 0; } int find(int x,int low) { int i,a=0; if(x==N) return low; for(i=1;i<=N;i++) { if(map[x][i]>0&&dis[i]==dis[x]+1&&(a=find(i,min(low,map[x][i])))) { map[x][i]-=a; map[i][x]+=a; return a; } } return 0; } int main(void) { int i,f,t,flow,tans; while(~scanf("%d%d",&M,&N)) { memset(map,0,sizeof(map)); for(i=1;i<=M;i++) { scanf("%d%d%d",&f,&t,&flow); map[f][t]+=flow; } ANS=0; while(BFS()) { while(tans=find(1,0x3f3f3f3f)) ANS+=tans; } printf("%d\n",ANS); } }
第二个版本Dinic
#include<iostream> #include<queue> using namespace std; #define INF 0x3f3f3f3f #define N 210 #define min(x,y) ((x>y)?(y):(x)) int map[N][N]; bool vis[N]; int pre[N]; int m,n; bool bfs(int s,int t) { int p; queue<int>q; memset(pre,-1,sizeof(pre)); memset(vis,false,sizeof(vis)); pre[s]=s; vis[s]=true; q.push(s); while(!q.empty()) { p=q.front(); q.pop(); for(int i=1;i<=n;i++) { if(map[p][i]>0&&!vis[i]) { pre[i]=p; vis[i]=true; if(i==t) return true; q.push(i); } } } return false; } int EdmondsKarp(int s,int t) { int flow=0,d,i; while(bfs(s,t)) { d=INF; for(i=t;i!=s;i=pre[i]) d=min(d,map[pre[i]][i]); for(i=t;i!=s;i=pre[i]) { map[pre[i]][i]-=d; map[i][pre[i]]+=d; } flow+=d; } return flow; } int main(void) { while(~scanf("%d%d",&m,&n)) { int u,v,w; memset(map,0,sizeof(map)); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); map[u][v]+=w; } printf("%d\n",EdmondsKarp(1,n)); } }
