2015
04-13

# 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

HintThe map is like this:  

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

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

#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()
{

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;

{
//	k=q.front();
//	q.pop();
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;
}