Given a n*n matrix C
ij (1<=i,j<=n),We want to find a n*n matrix X
ij (1<=i,j<=n),which is 0 or 1.
Besides,X
ij meets the following conditions:
1.X
12+X
13+...X
1n=1
2.X
1n+X
2n+...X
n-1n=1
3.for each i (1<i<n), satisfies ∑X
ki (1<=k<=n)=∑X
ij (1<=j<=n).
For example, if n=4,we can get the following equality:
X
12+X
13+X
14=1
X
14+X
24+X
34=1
X
12+X
22+X
32+X
42=X
21+X
22+X
23+X
24
X
13+X
23+X
33+X
43=X
31+X
32+X
33+X
34
Now ,we want to know the minimum of ∑C
ij*X
ij(1<=i,j<=n) you can get.
Hint
For sample, X
12=X
24=1,all other X
ij is 0.
Input
The input consists of multiple test cases (less than 35 case).
For each test case ,the first line contains one integer n (1<n<=300).
The next n lines, for each lines, each of which contains n integers, illustrating the matrix C, The j-th integer on i-th line is C
ij(0<=C
ij<=100000).
Output
For each case, output the minimum of ∑C
ij*X
ij you can get.
Sample Input
4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2
Sample Output
3
好题！
一开始拿到题的时候是无解的，后来发现还可以这么巧秒！
其实这对应了图的两种情况（一开始没想到第二种疯狂WA）
1.1-n节点的最短路
2.1出发（不自环）绕一圈后回到1，从n出发（同样不自环）绕一圈后回到n同样满足题意
题目就转化成了求1-n的最短路与1与n的最小环的和的最小值问题
代码如下
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int mapp[380][380];
int dist[380];
int vis[380],n;
void init()
{
for(int i=1; i<=n; i++)
{
vis[i]=0;
dist[i]=0x3f3f3f3f;
}
}
int dij(int s,int &ans)//开始点即循环起点
{
init();
dist[s]=0;
for(int i=0; i<n; i++)
{
int v,minn=0x3f3f3f3f;
for(int j=1; j<=n; j++)
{
if(!vis[j]&&dist[j]<minn)
minn=dist[v=j];
}
vis[v]=1;
for(int j=1; j<=n; j++)
{
if(!vis[j]&&dist[j]>dist[v]+mapp[v][j])
dist[j]=dist[v]+mapp[v][j];
if(j==s&&s!=v)
{
ans=min(ans,dist[v]+mapp[v][j]);
}
}
}
return dist[n];
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d",&mapp[i][j]);
}
}
int key1,key2=0x3f3f3f3f,key3=0x3f3f3f3f;
key1=dij(1,key2);
dij(n,key3);
printf("%d\n",min(key1,key2+key3));
}
}
