首页 > ACM题库 > HDU-杭电 > HDU 4370-0 or 1-图-[解题报告]HOJ
2015
05-24

HDU 4370-0 or 1-图-[解题报告]HOJ

0 or 1

问题描述 :

Given a n*n matrix Cij (1<=i,j<=n),We want to find a n*n matrix Xij (1<=i,j<=n),which is 0 or 1.

Besides,Xij meets the following conditions:

1.X12+X13+…X1n=1
2.X1n+X2n+…Xn-1n=1
3.for each i (1<i<n), satisfies ∑Xki (1<=k<=n)=∑Xij (1<=j<=n).

For example, if n=4,we can get the following equality:

X12+X13+X14=1
X14+X24+X34=1
X12+X22+X32+X42=X21+X22+X23+X24
X13+X23+X33+X43=X31+X32+X33+X34

Now ,we want to know the minimum of ∑Cij*Xij(1<=i,j<=n) you can get.

Hint

For sample, X12=X24=1,all other Xij is 0.

输入:

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 Cij(0<=Cij<=100000).

输出:

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 Cij(0<=Cij<=100000).

样例输入:

4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2

样例输出:

3

一道非常巧妙的题目,引用别人博客的话就是“将完全没有思路的一道题目一下子编程了简单的最短路”

当然,最短路还不是问题的全解,后来众牛发现除了最短路还有一个最小花费环的情况。

贴一下官方的题解:(http://page.renren.com/601081183/note/866168965

//////

1001  (已更新)

显然,题目给的是一个0/1规划模型。



解题的关键在于如何看出这个模型的本质。



3个条件明显在刻画未知数之间的关系,从图论的角度思考问题,容易得到下面3个结论:



1.X12+X13+…X1n=1 于是1号节点的出度为1



2..X1n+X2n+…Xn-1n=1 于是n号节点的入度为1



3.∑Xki =∑Xij 于是2~n-1号节点的入度必须等于出度



于是3个条件等价于一条从1号节点到n号节点的路径,故Xij=1表示需要经过边(i,j),代价为Cij。Xij=0表示不经过边(i,j)。注意到Cij非负且题目要求总代价最小,因此最优答案的路径一定可以对应一条简单路径。



最终,我们直接读入边权的邻接矩阵,跑一次1到n的最短路即可,记最短路为path。



以上情况设为A



非常非常非常非常非常非常非常非常抱歉,简单路径只是充分条件,但不必要。(对造成困扰的队伍深表歉意)



漏了如下的情况B:



从1出发,走一个环(至少经过1个点,即不能是自环),回到1;从n出发,走一个环(同理),回到n。



容易验证,这是符合题目条件的。且A || B为该题要求的充要条件。



由于边权非负,于是两个环对应着两个简单环。



因此我们可以从1出发,找一个最小花费环,记代价为c1,再从n出发,找一个最小花费环,记代价为c2。(只需在最短路算法更新权值时多加一条记录即可:if(i==S) cir=min(cir,dis[u]+g[u][i]))



故最终答案为min(path,c1+c2)

////////

官方的标程是dijkstra+head(优先队列)

本来想改一下官方的标程算了,毕竟最短路不难。后来发现优先队列的最短路貌似和想象有点不同….

于是就有了普通版的dijkstra=   =(+最小花费环)


#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min;
const int maxx = 310;
int edge[maxx][maxx];
int dist[maxx];
int s[maxx];
const int INF = 33686018;
int n;
int dijkstra(int u0,int& cir)
{
    for(int i=1; i<=n; i++)
    {
        dist[i] = edge[u0][i];
        s[i] = 0;
    }
    dist[u0] = 0;
    s[u0] = 1;
    for(int i=2; i<=n; i++)
    {
        int minn = INF;
        int u = u0;
        for(int j=1; j<=n; j++)
        {
            if(!s[j] && dist[j]<minn)
            {
                minn = dist[j];
                u = j;
            }
        }
        s[u] = 1;
        for(int j=1; j<=n; j++)
        {
            if(!s[j] && edge[u][j]<INF && dist[u] + edge[u][j] < dist[j])
                dist[j] = dist[u] + edge[u][j];
            if(j==u0 && u!=u0)
                cir = min(cir,dist[u] + edge[u][j]);
        }
    }
    return dist[n];
}
int main()
{
//    freopen("1001.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                scanf("%d",&edge[i][j]);
        int cir_u0,cir_n,cir;
        cir_u0 = cir_n = cir = INF;
        int dis = dijkstra(1,cir_u0);
        dijkstra(n,cir_n);
        cir = cir_u0 + cir_n;
        printf("%d\n",min(dis,cir));
    }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/h2952220/article/details/7877013