HDU - 4370 0 or 1

0 or 1

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2811    Accepted Submission(s): 914

Problem 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₁₂+X₁₃+...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₁₂+X₁₃+X₁₄=1
X₁₄+X₂₄+X₃₄=1
X₁₂+X₂₂+X₃₂+X₄₂=X₂₁+X₂₂+X₂₃+X₂₄
X₁₃+X₂₃+X₃₃+X₄₃=X₃₁+X₃₂+X₃₃+X₃₄

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

Hint

For sample, X₁₂=X₂₄=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

 题目链接 

模型转换得很巧妙。。详情看kuangbin大神的博客。

https://www.cnblogs.com/kuangbin/archive/2012/08/17/2644557.html

/*
HDU 4370 0 or 1
转换思维的题啊，由一道让人不知如何下手的题，转换为了最短路
基本思路就是把矩阵看做一个图，图中有n个点，1号点出度为1，
n号点入度为1，其它点出度和入度相等，路径长度都是非负数，

等价于一条从1号节点到n号节点的路径，故Xij=1表示需要经
过边(i,j)，代价为Cij。Xij=0表示不经过边(i,j)。注意到Cij非负
且题目要求总代价最小，因此最优答案的路径一定可以对应一条简单路径。

最终，我们直接读入边权的邻接矩阵，跑一次1到n的最短路即可，记最短路为path。

漏了如下的情况B：
从1出发，走一个环（至少经过1个点，即不能
是自环），回到1；从n出发，走一个环（同理），回到n。
也就是1和n点的出度和入度都为1，其它点的出度和入度为0.

由于边权非负，于是两个环对应着两个简单环。

因此我们可以从1出发，找一个最小花费环，记代价为c1,
再从n出发，找一个最小花费环，记代价为c2。
（只需在最短路算法更新权值时多加一条记录即可：if(i==S) cir=min(cir,dis[u]+g[u][i])）

故最终答案为min(path,c1+c2)
*/
/*
本程序用SPFA来完成最短路。
但是由于要计算从出发点出发的闭环的路径长度。
所以要在普通SPFA的基础上做点变化。

就是把dist[start]设为INF。同时一开始并不是让出发点入队，而是让
出发点能够到达的点入队。
*/
//以上来自kuangbin的blog

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include <queue>
#include <vector>
#include<bitset>
using namespace std;
typedef long long LL;
const int maxn = ;
const int mod = +;
typedef pair<int,int> pii;
#define X first
#define Y second
#define pb push_back
//#define mp make_pair
#define ms(a,b) memset(a,b,sizeof(a))

const int inf = 0x3f3f3f3f;
int cost[maxn][maxn];
int dist[maxn];
int que[maxn];
bool vis[maxn];

void spfa(int st,int n){
    int fro =  ,rear = ;
    for(int i=;i<=n;i++){
        if(i==st){
            dist[i]=inf;
            vis[i]=false;
        }else if(cost[st][i]!=inf){
            dist[i]=cost[st][i];
            que[rear++]=i;
            vis[i]=true;
        }else{
            dist[i]=inf;
            vis[i]=false;
        }
    }

    while(fro!=rear){
        int u = que[fro++];
        for(int v=;v<=n;v++){
            if(dist[v]>dist[u]+cost[u][v]){
                dist[v]=dist[u]+cost[u][v];
                if(!vis[v]){
                    vis[v]=true;
                    que[rear++]=v;
                    if(rear>=maxn) rear=;
                }
            }
        }
        vis[u]=false;
        if(fro>=maxn) fro=;
    }
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=;i<=n;i++){
            for(int j=;j<=n;j++){
                scanf("%d",&cost[i][j]);
            }
        }
        spfa(,n);
        int ans=dist[n];
        int loop1=dist[];
        spfa(n,n);
        int loop2=dist[n];
        ans=min(ans,loop1+loop2);
        cout<<ans<<endl;
    }
}