HDU 4370 0 or 1（最短路）

转载自：http://blog.csdn.net/qq_21057881/article/details/52128980

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

思路：一个很裸的0/1规划的题，没接触过的话很难会朝图论的方面去想，从前两个条件其实就是点1的出度为1，点n的入度为1，然后其他点的出度等于入度，边权就是它的费用，那么建图然后最短路就可以了，这里比较坑的是由于只说了出度为1，但入度不知道，所以可能存在两个环，从1出发回到1，从n出发回到n的情况

#include <iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; #define inf 1e9 const int maxn = 400; int n,mp[maxn][maxn]; int d[maxn],inq[maxn]; int spfa(int s,int t,int &res) { queue<int>q; for(int i = 0;i<=n;i++) d[i]=inf; memset(inq,0,sizeof(inq)); d[s]=0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); inq[u]=0; for(int i = 0;i<n;i++) { if(s!=u && i==s) res = min(res,mp[u][i]+d[u]); if(d[i]>d[u]+mp[u][i]) { d[i]=d[u]+mp[u][i]; if(!inq[i]) { q.push(i); inq[i]=1; } } } } return d[t]; } int main() { while(scanf("%d",&n)!=EOF) { for(int i = 0;i<n;i++) for(int j = 0;j<n;j++) scanf("%d",&mp[i][j]); int res1 = inf; int ans = spfa(0,n-1,res1); int res2 = inf; spfa(n-1,0,res2); printf("%d\n",min(ans,res1+res2)); } }