はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

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;
}

増加パスの流量を求めるのに、再帰で最小値を求めていくという発想に感動しました。
無理。