GRL_6_A Maximum Flow
問題
最大流 | グラフ | Aizu Online Judge
最大流の問題です。フォード・ファルカーソンのアルゴリズムにて実装しました。
アルゴリズム自体はなんとなーーーーく分かったのですが、実装は全く手が動きませんでした。
というわけで蟻本のコードをほぼそのまま写しました。
#include<stdio.h> #include<string.h> #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MAX 100 #define INF 100000000 int adj[MAX][MAX]; int visited[MAX]; int v; int dfs(int u,int t,int f){ int i; if(u == t)return f; visited[u]=1; for(i=0;i<v;i++){ if(visited[i]==0 && adj[u][i]>0){ int d=dfs(i,t,MIN(f,adj[u][i])); if(d > 0){ adj[u][i]-=d; adj[i][u]+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; while(1){ memset(visited,0,sizeof(visited)); int f=dfs(s,t,INF); if(f==0)return flow; flow+=f; } return 0; } int main(){ int e; int x,y,z,i,j; scanf("%d %d",&v,&e); for(i=0;i<v;i++){ for(j=0;j<v;j++){ adj[i][j]=0; } } for(i=0;i<e;i++){ scanf("%d %d %d",&x,&y,&z); adj[x][y]=z; } printf("%d\n",max_flow(0,v-1)); return 0; }
増加パスの流量を求めるのに、再帰で最小値を求めていくという発想に感動しました。
無理。