0 or 1

题目

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

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: 

12+X 13+X 14=1 
14+X 24+X 34=1 
12+X 22+X 32+X 42=X 21+X 22+X 23+X 24 
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.    思路:对于给的矩阵和等式可以这么理解,给的矩阵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 }

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄