0 or 1 HDU - 4370-有解無憂

0 or 1

題目：

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. 思路：對于給的矩陣和等式可以這么理解，給的矩陣C看作距離矩陣，表示兩點之間邊的距離，等式① -> 點1的出度為1 等式② -> 點n的入度為1 等式③ -> 點2 ~ n-1 的入度等于出度而Xij是一個01矩陣，即任意兩點之間是否有變存在，則 ∑C _ij*X _{ij容易理解為一條路徑的長度，而這條路徑有兩種情況：} A：點1出發到達點n的最短距離，記作ans， B：點1出發回到點1的最短距離，點n出發回到點n最短距離，兩個環的答案相加：d1 + d2，最后的答案就是 min(A, B)，如何得出環的最小距離呢，我們可以用spfa，讓出發點的dis[start] = INF，然后其他點就是dis[v] = dis[start][v]，最后dis[start]就是換的最小距離，

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <vector>
 6 #include <cmath>
 7 
 8 using namespace std;
 9 
10 #define ll long long
11 #define pb push_back
12 #define fi first
13 #define se second
14 
15 const int N = 310;
16 const int INF = 1e9;
17 int G[N][N];
18 int dis[N];
19 bool vis[N];
20 queue<int > que;
21 int n;
22 
23 int SPFA(int s)
24 {
25     for(int i = 1; i <= n; ++i){
26         if(i == s){
27             vis[i] = false;
28             dis[i] = INF;
29         }else{
30             vis[i] = true;
31             dis[i] = G[s][i];
32             que.push(i);
33         }
34     }
35 
36     while(!que.empty()){
37         int now = que.front();
38         que.pop();
39         vis[now] = false;
40 
41         for(int i = 1; i <= n; ++i){
42             if(dis[i] > dis[now] + G[now][i]){
43                 dis[i] = dis[now] + G[now][i];
44                 if(!vis[i]) que.push(i);
45             }
46         }
47     }
48 
49     return dis[s];
50 }
51 
52 void solve()
53 {
54     while(~scanf("%d", &n)){
55         for(int i = 1; i <= n; ++i){
56             for(int j = 1; j <= n; ++j)
57                 scanf("%d", &G[i][j]);
58         }
59 
60         int d1 = SPFA(1);
61         int ans = dis[n];
62         int d2 = SPFA(n);
63         //printf("dis = %d\n", min(d1 + d2, ans));
64         printf("%d\n", min(d1 + d2, ans));
65     }
66 }
67 
68 int main()
69 {
70 
71     solve();
72 
73     return 0;
74 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27701.html

標籤：其他

上一篇：6.排序總結和優化

下一篇：0264. Ugly Number Ⅱ (M)