2015
05-24

# 0 or 1

Given a n*n matrix Cij (1<=i,j<=n),We want to find a n*n matrix Xij (1<=i,j<=n),which is 0 or 1.

Besides,Xij meets the following conditions:

1.X12+X13+…X1n=1
2.X1n+X2n+…Xn-1n=1
3.for each i (1<i<n), satisfies ∑Xki (1<=k<=n)=∑Xij (1<=j<=n).

For example, if n=4,we can get the following equality:

X12+X13+X14=1
X14+X24+X34=1
X12+X22+X32+X42=X21+X22+X23+X24
X13+X23+X33+X43=X31+X32+X33+X34

Now ,we want to know the minimum of ∑Cij*Xij(1<=i,j<=n) you can get.

Hint

For sample, X12=X24=1,all other Xij is 0.

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 Cij(0<=Cij<=100000).

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 Cij(0<=Cij<=100000).

4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2

3

//////

1001  (已更新)

3个条件明显在刻画未知数之间的关系，从图论的角度思考问题，容易得到下面3个结论：

1.X12+X13+…X1n=1 于是1号节点的出度为1

2..X1n+X2n+…Xn-1n=1 于是n号节点的入度为1

3.∑Xki =∑Xij 于是2~n-1号节点的入度必须等于出度

////////

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min;
const int maxx = 310;
int edge[maxx][maxx];
int dist[maxx];
int s[maxx];
const int INF = 33686018;
int n;
int dijkstra(int u0,int& cir)
{
for(int i=1; i<=n; i++)
{
dist[i] = edge[u0][i];
s[i] = 0;
}
dist[u0] = 0;
s[u0] = 1;
for(int i=2; i<=n; i++)
{
int minn = INF;
int u = u0;
for(int j=1; j<=n; j++)
{
if(!s[j] && dist[j]<minn)
{
minn = dist[j];
u = j;
}
}
s[u] = 1;
for(int j=1; j<=n; j++)
{
if(!s[j] && edge[u][j]<INF && dist[u] + edge[u][j] < dist[j])
dist[j] = dist[u] + edge[u][j];
if(j==u0 && u!=u0)
cir = min(cir,dist[u] + edge[u][j]);
}
}
return dist[n];
}
int main()
{
//    freopen("1001.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&edge[i][j]);
int cir_u0,cir_n,cir;
cir_u0 = cir_n = cir = INF;
int dis = dijkstra(1,cir_u0);
dijkstra(n,cir_n);
cir = cir_u0 + cir_n;
printf("%d\n",min(dis,cir));
}
}