hdu 4370 0 or 1 （最短路）

hdu 4370 0 or 1

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

Hint

For sample, X 12=X 24=1,all other X ij is 0.

題目大意：有一個矩陣C[i][j]，和一個由01組成的矩陣X[i][j]。X矩陣滿足條件：

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).

現在要求最小的∑C ij*X ij。

解題思路：思維轉換過來就好做了。從第一個條件可以看出一號結點出度為1，從第二個條件可以看出n號節點的入度為1，從第三個條件可以看出2~n-1號節點的入度必須等於出度。所以可以直接把C[i][j]看成是一張鄰接矩陣，1為起點，n為終點，跑一次最短路，求出最短路sp。

這是其中一種情況，還有另一種情況滿足題目條件，就是，1號結點有非自環的閉環，n號結點也有非自環的閉環。以1為起點，但d[1]置為INF，且起點不入隊列，而讓，與1號結點連向的點進入隊列，然後跑最短路，最後d[1]就是1結點的最小閉環b1，n的最小閉環b2同理。

所以最後答案就是min(sp, b1 + b2)。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 305;
const int M = 90000;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int n, Gra[N][N];
int d[N], vis[N], en;
int head[M];

struct node {  
    int to, dis, next;  
}edge[M];  

void addEdge(int u,int v,int x) {  
    edge[en].to = v;  
    edge[en].next = head[u];  
    edge[en].dis = x;  
    head[u] = en++;  
}  

void SPFA(int s) {  
    queue Q;   
    for (int i = 0; i <= n; i++) d[i] = INF;
    for (int i = head[s]; i != -1; i = edge[i].next) {
        int v = edge[i].to; 
        if (v == s) continue;
        d[v] = edge[i].dis;
        Q.push(v);
        vis[v] = 1;
    }
    while(!Q.empty()) {  
        int u = Q.front();
        Q.pop();  
        vis[u] = 0;  
        for(int i = head[u]; i != -1; i = edge[i].next) {  
            int v = edge[i].to;  
            if(d[u] + edge[i].dis < d[v]) {  
                d[v] = d[u] + edge[i].dis;  
                if(!vis[v]) {  
                    Q.push(v);  
                    vis[v] = 1;  
                }  
            }  
        }  
    }  
} 

void init() {
    en = 0;
    for (int i = 0; i <= n; i++) {
        vis[i] = 0; 
        head[i] = -1;
    }
}

void input() {
    int a;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf(%d, &a);
            addEdge(i, j, a);
        }   
    }
}
void solve() {
    SPFA(1);    
    int ans = d[n], temp1 = d[1];
    SPFA(n);
    int temp2 = d[n];
    printf(%d
, min(ans, temp1 + temp2));
}

int main() {
    while (scanf(%d, &n) != EOF) {
        init();
        input();
        solve();
    }
    return 0;
}