首页 > ACM题库 > HDU-杭电 > HDU 3870-Catch the Theves-图-[解题报告]HOJ
2015
04-13

HDU 3870-Catch the Theves-图-[解题报告]HOJ

Catch the Theves

问题描述 :

A group of thieves is approaching a museum in the country of zjsxzy,now they are in city A,and the museum is in city B,where keeps many broken legs of zjsxzy.Luckily,GW learned the conspiracy when he is watching stars and told it to zjsxzy.
Zjsxzy decided to caught these thieves,and he let the police to do this,the police try to catch them on their way from A to B. Although the thieves might travel this way by more than one group, zjsxzy’s excellent police has already gather the statistics that the cost needed on each road to guard it.
Now ,zjsxzy’s conutry can be described as a N*N matrix A,Aij indicates the city(i,j) have bidirectionals road to city(i+1,j) and city(i,j+1),gurad anyone of them costs Aij.
Now give you the map,help zjsxzy to calculate the minimium cost.We assume thieves may travel in any way,and we will catch all passing thieves on a road if we guard it.

输入:

The first line is an integer T,followed by T test cases.
In each test case,the first line contains a number N(1<N<=400).
The following N lines,each line is N numbers,the jth number of the ith line is Aij.
The city A is always located on (1,1) and the city B is always located on (n,n).
Of course,the city (i,j) at the last row or last line won’t have road to (i,j+1) or (i+1,j).

输出:

The first line is an integer T,followed by T test cases.
In each test case,the first line contains a number N(1<N<=400).
The following N lines,each line is N numbers,the jth number of the ith line is Aij.
The city A is always located on (1,1) and the city B is always located on (n,n).
Of course,the city (i,j) at the last row or last line won’t have road to (i,j+1) or (i+1,j).

样例输入:

1
3
10 5 5
6 6 20
4 7 9

样例输出:

18

Hint
The map is like this:
Color the Simple Cycle

        题意:N*N的方格,每条边有权值,求从(1,1)到(n,n)的最小割。n<=400

        这题是在S-T平面图中将最小割转化为最短路的题,推荐08年OI论文周冬《两极相通——浅析最大—最小定理在信息学竞赛中的应用》,没看论文的压力很大,果断不会。研究了一会,下面说下自己的理解。

何为S-T平面图:首先是一平面图(满足欧拉公式与存在对偶图),且源点S,汇点T在边界上。

如何构造对偶图:将S-T连线,将最外面的一个大面(无限大)一分为二了,一个为S*,一个为T*,然后将跨跃某条边的两个面连线,再去掉S*与T*的连线。从下图就可看出S*到T*的一条路径就会对应一个S至T割,S*到T*的最短路就对应最小割了,然后求S*到T*的最短路即可。如图

Catch the Theves

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int maxn=170000;

struct point
{
	int v,w;
}p0;

vector<point> e[maxn];
//queue<int>q;//
int n,S,T,q[maxn];
int dist[maxn];
bool inq[maxn];
int SPFA()
{
	int i,k,head=0,tail=0;

	memset(inq,false,sizeof(inq));
	for(i=0;i<=(n-1)*(n-1)+1;i++)
		dist[i]=0x3fffffff;
//	while(!q.empty()) q.pop();
//	q.push(S);
	q[tail++]=S;
	dist[S]=0;
	inq[S]=true;

	while(head!=tail)
	{
	//	k=q.front();
	//	q.pop();
		k=q[head];
		head=(head+1)%maxn;
		inq[k]=false;
		for(i=0;i<e[k].size();i++)
		{
			p0=e[k][i];
			if(dist[p0.v]>dist[k]+p0.w)
			{
				dist[p0.v]=dist[k]+p0.w;
				if(!inq[p0.v])
				{
					inq[p0.v]=true;
					q[tail]=p0.v;
					tail=(tail+1)%maxn;
				//	q.push(p0.v);
				}
			}
		}
	}
	return dist[T];
}

int main()
{
	int t,i,j,k;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=0;i<(n-1)*(n-1)+2;i++)
			e[i].clear();
		S=(n-1)*(n-1);
		T=(n-1)*(n-1)+1;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%d",&k);
				p0.w=k;
				if(i==0&&j!=n-1)
				{
					p0.v=j;
					e[S].push_back(p0);
				//	p0.v=S;
				//	e[j].push_back(p0);
				}
				if(j==n-1&&i!=n-1)
				{
					p0.v=i*(n-1)+j-1;
					e[S].push_back(p0);
				//	p0.v=S;
				//	e[i*(n-1)+j-1].push_back(p0);
				}
				if(j==0&&i!=n-1)
				{
					p0.v=T;
					e[i*(n-1)].push_back(p0);
				//	p0.v=i*(n-1);
				//	e[T].push_back(p0);
				}
				if(i==n-1&&j!=n-1)
				{
					p0.v=T;
					e[(n-2)*(n-1)+j].push_back(p0);
				//	p0.v=(n-2)*(n-1)+j;
				//	e[T].push_back(p0);
				}

				if(i!=n-1&&j!=n-1)
				{
					if(i)
					{
						p0.v=(i-1)*(n-1)+j;
						e[i*(n-1)+j].push_back(p0);
						p0.v=i*(n-1)+j;
						e[(i-1)*(n-1)+j].push_back(p0);
					}
					if(j)
					{
						p0.v=i*(n-1)+j-1;
						e[i*(n-1)+j].push_back(p0);
						p0.v=i*(n-1)+j;
						e[i*(n-1)+j-1].push_back(p0);
					}
				}
			}
		}

		printf("%d\n",SPFA());
	}
	return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ahero_happy/article/details/6637214


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。