首页 > ACM题库 > HDU-杭电 > HDU 3616-Escape From Huarong Road[解题报告]HOJ
2014
11-29

HDU 3616-Escape From Huarong Road[解题报告]HOJ

Escape From Huarong Road

问题描述 :

The Chibi Battle is perhaps the most famous battle in the history of China. Liu Bei and Sun Quan won the battle after using a series of wonderful stratagem. Now, they are going to catch the leader of their enemy Cao Cao.

In order to help Cao Cao to escape, the soldiers of Cao Cao have been divided into several parts, and Cao Cao is in one of these part. Now they are all in a rectangle area which can be divided into many squares of the equal size. Once the soldiers get out of this area, they escape successfully.

Because Liu Bei and Sun Quan don’t know exactly which part Cao Cao is in, so they all Cao Cao’s soldiers.

In this area, some squares are lawns that can be passed, while some squares are Marshes that can’t be passed. Liu Bei and SunQuan decide to set fire on lawns to those squares can’t be passed. Because some reasons, set fire on different squares needs different length of time. And they can only set fire on one square at the same time. Now, Cao Cao and all his soldiers are having rest and you can assume that they won’t move. Liu Bei and SunQuan want to know how much time they need at least to set fire to make Cao Cao and all his soldiers can’t escape any way when they want to move. Can you help them?

输入:

The first line in the input file is a single integer: T (1 ≤ T ≤ 10), representing the number of test cases. For each test case, in the first line there are two integers: r and c (1 ≤ r, c ≤ 30) – the height and length of the area. Then there are r lines, in each line there are c integers. The j-th integer in the i-th line is mij. Each of these integers describes a square: if tij is positive, then the square is a lawn and it needs mij unit of time to set fire on it; if mij is 0, it means some soldiers of Cao Cao are having rest in this square; if mij is -1, means the square can’t be passed.

When Cao Cao and his soldiers move, they can only move to a square that share an edge with the square they are in just now. All positive integers in the input file are smaller or equal to 100.

输出:

The first line in the input file is a single integer: T (1 ≤ T ≤ 10), representing the number of test cases. For each test case, in the first line there are two integers: r and c (1 ≤ r, c ≤ 30) – the height and length of the area. Then there are r lines, in each line there are c integers. The j-th integer in the i-th line is mij. Each of these integers describes a square: if tij is positive, then the square is a lawn and it needs mij unit of time to set fire on it; if mij is 0, it means some soldiers of Cao Cao are having rest in this square; if mij is -1, means the square can’t be passed.

When Cao Cao and his soldiers move, they can only move to a square that share an edge with the square they are in just now. All positive integers in the input file are smaller or equal to 100.

样例输入:

1
4 3
1 2 1
1 10 1
1 0 -1
1 1 1

样例输出:

6

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn = 40;
const int maxpot = maxn*maxn*2;
const int maxm = maxpot*10;
const int INFI = 99999999;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

int a[maxn][maxn];
int idx[maxn][maxn];
int L[maxpot],R[maxpot];
int head[maxpot],dep[maxpot],lis[maxpot];
int next[maxm],pot[maxm],flow[maxm];
int S,T,tot,n,m;

void addedge(int a,int b,int c)
{
	pot[++tot] = b; next[tot] = head[a];
	head[a] = tot; flow[tot] = c;
}
void connect(int a,int b,int c)
{
	addedge(a,b,c);
	addedge(b,a,0);
}
bool bfs()
{
	for (int i=0;i<=T;i++) dep[i] = 0;
	int h=1,t=1;
	lis[1] = S;
	dep[S] = 1;
	while ( h<=t )
	{
		int v = lis[h];
		for (int e=head[v];e!=-1;e=next[e])
		if ( flow[e]>0 && dep[pot[e]]==0 )
		{
			dep[pot[e]] = dep[v] + 1;
			lis[++t] = pot[e];
		}
		h++;
	}
	return dep[T]>0;
}
int findpath(int v,int tmpflow)
{
	if ( v==T ) return tmpflow;
	int rec = 0,tmp;
	for (int e=head[v];e!=-1;e=next[e])
	if ( flow[e]>0 && dep[pot[e]]==dep[v]+1 )
	{
		tmp = findpath(pot[e],min(tmpflow,flow[e]));
		tmpflow -= tmp; rec += tmp;
		flow[e] -= tmp; flow[e^1] += tmp;
		if ( tmpflow==0 ) break;
	}
	dep[v] = 0;
	return rec;
}
int dinic()
{
	int ret = 0;
	while ( bfs() )
		ret += findpath(S,INFI);
	return ret;
}
void debug()
{
	for (int i=0;i<=T;i++)
	{
		printf("connect %d is ",i);
		for (int e=head[i];e!=-1;e=next[e])
		{
			if ( flow[e]>0 )
				printf("(%d,%d) ",pot[e],flow[e]);
		}
		printf("\n");
	}
}
void build_graph()
{
	int sum = 0;
	int tx,ty;
	int v,u;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		if ( a[i][j]!=-1 )
			idx[i][j] = ++sum;
			
	S = 0;
	for (int i=1;i<=sum;i++)
	{
		L[i] = i;
		R[i] = i + sum;
	} 
	T = 2 * sum + 1;
	memset(head,-1,sizeof(head));
	tot = -1;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		if ( a[i][j]!=-1 )
		{
			v = idx[i][j];
			//printf("v is %d\n",v);
			if ( a[i][j]!=0 )
				connect(L[v],R[v],a[i][j]);
			else
				connect(L[v],R[v],INFI);
				
			for (int t=0;t<4;t++)
			{
				tx = i + dx[t];
				ty = j + dy[t];
				if ( tx<0 || ty<0 || tx>=n || ty>=m ) continue;
				u = idx[tx][ty];
				if ( a[tx][ty]!=-1 )
					connect(R[v],L[u],INFI);	
			}
			if ( a[i][j]==0 )
				connect(S,L[v],INFI);
			if ( i==0 || j==0 || i==n-1 || j==m-1 )
				connect(R[v],T,INFI);
		}
	//debug();
}
int main()
{
	int test;
	scanf("%d",&test);
	for (int cas=1;cas<=test;cas++)
	{
		scanf("%d%d",&n,&m);
		for (int i=0;i<n;i++)
			for (int j=0;j<m;j++)
				scanf("%d",&a[i][j]);
		build_graph();
		int ans = dinic();
		printf("%d\n",ans);
	}
}