글 읽기 - 네트워크 플로우 코딩 **코드 포함**

medic_programmer 8년 전 0

평소 네트워크 플로우 코딩이 너무 복잡하고 어려워요...

제가 너무 복잡하게 코딩하는거같은데 Tip좀 주실수있나요

#include<stdio.h>

int n,m,d[5001][5001],f[5001][5001],rear,front;
bool chk[5001];

struct data
{
	int node,flow,from;
}; data queue[5000001];

void process()
{
	int i,j;
	
	for(i=0; i<=n*m+1; i++)	for(j=0; j<=n*m+1; j++) d[i][j] = 0;
	
	for(i=1; i<=n; i++){
		for(j=1; j<=m; j++){
			if(f[i][j] == 0) continue;
			if((i+j) % 2 == 0){
				d[0][(i-1)*m+j] = f[i][j];
				if(i!=1) d[(i-1)*m+j][(i-2)*m+j] = 999999999;
				if(i!=n) d[(i-1)*m+j][i*m+j] = 999999999;
				if(j!=1) d[(i-1)*m+j][(i-1)*m+j-1] = 999999999;
				if(j!=m) d[(i-1)*m+j][(i-1)*m+j+1] = 999999999;
			}
			else d[(i-1)*m+j][n*m+1] = f[i][j];
		}
	}
}

int minval(int a,int b)
{
	return a>b?b:a;
}

int network_flow()
{
	int i,nn,ff,now,val,fr,fr_node,now_node,j;
	
	rear = front = 0;
	
	for(i=0; i<=n*m+1; i++) chk[i] = false;
	
	queue[++front].node = 0;
	queue[front].flow = 999999999;
	queue[front].from = -1;
	chk[0] = true;
	
	rear++;
	for(i=1; i<=n; i++){
		for(j=1; j<=m; j++){
			if(d[0][(i-1)*m+j] > 0 && (i+j)%2 == 0){
				queue[++front].node = (i-1)*m+j;
				chk[(i-1)*m+j] = true;
				queue[front].flow = d[0][(i-1)*m+j];
				queue[front].from = rear;
			}
		}
	}
	
	while(1){
		nn = queue[++rear].node;
		ff = queue[rear].flow;
		
		if(rear>front) return -1;
		
		if(nn % m != 0){
			i = nn + 1;
			if(d[nn][i] > 0 && !chk[i]){
				queue[++front].node = i;
				chk[i] = true;
				queue[front].flow = minval(ff,d[nn][i]);
				queue[front].from = rear;
			}
		}
		if(nn % m != 1){
			i = nn - 1;
			if(d[nn][i] > 0 && !chk[i]){
				queue[++front].node = i;
				chk[i] = true;
				queue[front].flow = minval(ff,d[nn][i]);
				queue[front].from = rear;
			}
		}
		if(nn > m){
			i = nn - m;
			if(d[nn][i] > 0 && !chk[i]){
				queue[++front].node = i;
				chk[i] = true;
				queue[front].flow = minval(ff,d[nn][i]);
				queue[front].from = rear;
			}
		}
		if(nn <= (n-1)*m){
			i = nn + m;
			if(d[nn][i] > 0 && !chk[i]){
				queue[++front].node = i;
				chk[i] = true;
				queue[front].flow = minval(ff,d[nn][i]);
				queue[front].from = rear;
			}
		}
		
		
		i = n*m+1;
		if(d[nn][i] > 0 && !chk[i]){
			queue[++front].node = i;
			chk[i] = true;
			queue[front].flow = minval(ff,d[nn][i]);
			queue[front].from = rear;
			break;
		}
	}
	
	now = front; val = queue[now].flow;
	
	while(1){
		fr = queue[now].from;
		fr_node = queue[fr].node;
		now_node = queue[now].node;
		
		if(fr == -1) break;
		d[fr_node][now_node] -= val;
		d[now_node][fr_node] += val;
		now = fr;
	}
	
	return val;
}

int main()
{
	int i,t,j,T,sum=0,aa,ans=0;
	freopen("input.txt","r",stdin);
	
	scanf("%d",&T);
	
	for(t=1; t<=T; t++){
		ans = sum = 0;
		scanf("%d%d",&n,&m);
		for(i=1; i<=n; i++){
			for(j=1; j<=m; j++){
				scanf("%d",&f[i][j]);
				sum += f[i][j];
			}
		}
		process();
	
		while(1){
			aa = network_flow();
			if(aa == -1) break; 
			ans += aa;
		}
		printf("%d\n",sum-ans);
	}
	
	return 0;
}