Description

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

题意： （先说直接翻译过来的）

给出nxn矩阵Ci,j 求01矩阵Xij满足

1.X 12+X 13+...X 1n=1
2.X 1n+X 2n+...X n-1n=1
3.X矩阵的第i行的和等于第i列的和

做法&思路：

是在最短路分类里的QAQ百思不得其解，先把示例画出来。

咦？有行有列，莫非是拆点了？对于示例选的边可以画出这个图：


好像X矩阵是用来控制C矩阵加边与否的耶

再编一组数据找找规律


看着怎么这么眼熟，我是不是可以从右边往左边加边啊

另一个图：

越想越觉得有道理啊，因为要求第i行和第i列的和相等，就相当于通过新加的边过渡行与列，拆点，连边，其他的边正常连接就好，交了 WA了

看讨论区 有这样一组示例 ，连接的是中间图，咦？怎么分开了，所以我们需要连一个6->5的边


这样就存在两个问题：

1.有可能1->6->5->10,怎么办？1->6 5->10赋成无穷大，不走它就得了

2.如果分成好多团怎么办？依旧只连6->5，因为中间那部分就相当于for each i (1<i<n), satisfies ∑X ki (1<=k<=n)=∑X ij (1<=j<=n)=0了

    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<queue>
    #include<cstdio>
    using namespace std;
    int n,m,x;
    const long long  MAXINT=0x3f3f3f3f;
    const int MAXNUM=609;
    long long dist[MAXNUM];
    long long A[MAXNUM][MAXNUM];
    void Dijkstra(int v0)
    {
        bool S[MAXNUM];// 判断是否已存入该点到S集合中
        for(int i=1; i<=n; ++i)
        {
            dist[i]=A[v0][i];
           // printf("%d    ",dist[i]);
            S[i]=false; // 初始都未用过该点
        }
       // dist[v0] = 0;
        S[v0]=true;
        for(int i=2; i<=n; i++)
        {
            long long mindist = MAXINT;
            int u = -1;// 找出当前未使用的点j的dist[j]最小值
            for(int j=1; j<=n; ++j)
            if((!S[j]) && dist[j]<mindist)
            {
                u = j;// u保存当前邻接点中距离最小的点的号码
                mindist = dist[j];
                //printf("%d        ",mindist);
            }
            S[u] = true;
            for(int j=1; j<=n; j++)
                if((!S[j]) && A[u][j]<MAXINT)
                {
                    if(dist[u] + A[u][j] < dist[j])     //在通过新加入的u点路径找到离v0点更短的路径
                    {
                        dist[j] = dist[u] + A[u][j];    //更新dis                    //记录前驱顶点
                    }
                }
        }
        return;
    }
    int main()
    {
       //freopen("in.txt","r",stdin);
        while(~scanf("%d",&n))
        {
            for(int i=1; i<=n*2; i++)
            {
                for(int j=1; j<=n*2; j++)
                    if(i-j==n) A[i][j]=0;
                    else A[i][j]=MAXINT;
            }
            for(int i=1;i<=n;i++)
                for(int j=1+n;j<=n*2;j++)
                    scanf("%I64d",&A[i][j]);
            A[1][n+1]=A[n][n+n]=MAXINT;
            A[n+1][n]=0;
           // A[1][1+n]=A[n][n*2]=MAXINT;
          //  for(int i=1;i<=2*n;i++)for(int j=1;j<=2*n;j++)printf("i=%d,j=%d,A=%d\n",i,j,A[i][j]);
            n=n+n;
            Dijkstra(1);
            //for(int i=n/2+1;i<=n;i++)
            printf("%I64d\n",dist[n]);
        }
        return 0;
    }