R

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.

InputThe 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).OutputFor each case, output the minimum of ∑C _ij*X _ij you can get.
Sample Input

Sample Output

这道题大致一看一脸懵，仔细一看还是懵。。。。。。。。

题意：

这个条件的意思就是从1这个点只能到到其他点中的一个点，简单一点就是1号点的出度为1

那么这个是n号点，只不过这个是n号点的入度为1

第三个条件就是除了一号点和n号点，其他点的出度等于入度

这个X是题上给出的限制条件，我们要使我们选出来的路符合这两个条件

既然X的值只能为0或1，那么我们只需要求从1到n的最小花费就可以了

就是求出来从起点到终点的最小花费，这个样子我们把题目上面输入的数存在邻接矩阵里面直接拿来用，这个矩阵正好满足上面三个条件，所以这是一个结果

但是我们要考虑环的存在，即起点形成一个环，终点n形成一个环，这个样子其他点的出入度为0也满足题意，但是要保证他不是自环，即必须保证有两个点

上代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int INF=0x3f3f3f3f;
 8 int w[305][305],d[305],dis[305];
 9 queue<int>r;
10 void spay(int start,int ends)
11 {
12     memset(d,INF,sizeof(d));
13     memset(dis,0,sizeof(dis));
14     for(int i=1;i<=ends;++i)
15     {
16         if(i!=start)
17         {
18             dis[i]=1;
19             d[i]=w[start][i];
20             r.push(i);
21         }
22         else
23         {
24             d[i]=INF;
25         }
26     }
27     while(!r.empty())
28     {
29         int x=r.front();
30         r.pop();
31         dis[x]=0;
32         for(int i=1;i<=ends;++i)
33         {
34             if(d[i]>d[x]+w[x][i])
35             {
36                 d[i]=d[x]+w[x][i];
37                 if(!dis[i])
38                 {
39                     dis[i]=1;
40                     r.push(i);
41                 }
42             }
43         }
44     }
45 }
46 int main()
47 {
48     int n;
49     while(~scanf("%d",&n))
50     {
51         memset(w,0,sizeof(w));
52         for(int i=1;i<=n;++i)
53         {
54             for(int j=1;j<=n;++j)
55                 scanf("%d",&w[i][j]);
56         }
57         int q1,q2;
58         spay(1,n);
59         q1=d[n];
60         q2=d[1];
61         spay(n,n);
62         q2+=d[n];
63         printf("%d
",min(q1,q2));
64     }
65     return 0;
66 }

View Code

网搜的代码：

  1 /*
  2 HDU 4370 0 or 1
  3 转换思维的题啊，由一道让人不知如何下手的题，转换为了最短路
  4 基本思路就是把矩阵看做一个图，图中有n个点，1号点出度为1，
  5 n号点入度为1，其它点出度和入度相等，路径长度都是非负数，
  6 
  7 等价于一条从1号节点到n号节点的路径，故Xij=1表示需要经
  8 过边(i,j)，代价为Cij。Xij=0表示不经过边(i,j)。注意到Cij非负
  9 且题目要求总代价最小，因此最优答案的路径一定可以对应一条简单路径。
 10 
 11 最终，我们直接读入边权的邻接矩阵，跑一次1到n的最短路即可，记最短路为path。
 12 
 13 漏了如下的情况B：
 14 从1出发，走一个环（至少经过1个点，即不能
 15 是自环），回到1；从n出发，走一个环（同理），回到n。
 16 也就是1和n点的出度和入度都为1，其它点的出度和入度为0.
 17 
 18 由于边权非负，于是两个环对应着两个简单环。
 19 
 20 因此我们可以从1出发，找一个最小花费环，记代价为c1,
 21 再从n出发，找一个最小花费环，记代价为c2。
 22 （只需在最短路算法更新权值时多加一条记录即可：if(i==S) cir=min(cir,dis[u]+g[u][i])）
 23 
 24 故最终答案为min(path,c1+c2)
 25 */
 26 /*
 27 本程序用SPFA来完成最短路。
 28 但是由于要计算从出发点出发的闭环的路径长度。
 29 所以要在普通SPFA的基础上做点变化。
 30 
 31 就是把dist[start]设为INF。同时一开始并不是让出发点入队，而是让
 32 出发点能够到达的点入队。
 33 */
 34 #include<stdio.h>
 35 #include<iostream>
 36 #include<string.h>
 37 #include<algorithm>
 38 using namespace std;
 39 
 40 const int INF=0x3f3f3f3f;
 41 const int MAXN=330;
 42 int cost[MAXN][MAXN];//保存路径长度的邻接矩阵
 43 int dist[MAXN];
 44 int que[MAXN];//注意队列的循环利用，建成循环队列
 45 bool vis[MAXN];//是否在队列中标记
 46 
 47 void SPFA(int start,int n)
 48 {
 49     int front=0,rear=0;
 50     for(int v=1;v<=n;v++)//初始化
 51     {
 52         if(v==start)//由于要找start的闭环，所以dist[start]设为INF，且不入队
 53         {
 54             dist[v]=INF;
 55             vis[v]=false;
 56         }
 57         else if(cost[start][v]!=INF)
 58         {
 59             dist[v]=cost[start][v];
 60             que[rear++]=v;
 61             vis[v]=true;
 62         }
 63         else//即dist[start][v]==INF情况，对本题没有这种情况
 64         {
 65             dist[v]=INF;
 66             vis[v]=false;
 67         }
 68     }
 69 
 70     while(front!=rear)//注意这个条件是不等，因为是循环队列
 71     {
 72         int u=que[front++];
 73         for(int v=1;v<=n;v++)
 74         {
 75             if(dist[v]>dist[u]+cost[u][v])
 76             {
 77                 dist[v]=dist[u]+cost[u][v];
 78                 if(!vis[v])//不在队列
 79                 {
 80                     vis[v]=true;
 81                     que[rear++]=v;
 82                     if(rear>=MAXN) rear=0;//循环队列
 83                 }
 84             }
 85         }
 86         vis[u]=false;
 87         if(front>=MAXN)front=0;
 88     }
 89 
 90 }
 91 int main()
 92 {
 93     //freopen("in.txt","r",stdin);
 94     //freopen("out.txt","w",stdout);
 95     int n;
 96     while(scanf("%d",&n)!=EOF)
 97     {
 98         for(int i=1;i<=n;i++)
 99           for(int j=1;j<=n;j++)
100             scanf("%d",&cost[i][j]);
101         SPFA(1,n);
102         int ans=dist[n];//1到n的最短路
103         int loop1=dist[1];//1的闭环长度
104         SPFA(n,n);
105         int loopn=dist[n];//n的闭环长度
106         ans=min(ans,loop1+loopn);
107         printf("%d
",ans);
108     }
109     return 0;
110 }

View Code