d739. 最少路径覆盖＠Morris' Blog｜PChome Online 個人新聞台

2011-08-27 15:43:44| 人氣1,191| 回應0 | 上一篇 | 下一篇

d739. 最少路径覆盖

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

这题是一道关于图论的题目。

为了让大家容易理解题意，题目就没有什么背景啊、故事啊什么的。

就直接奔入主题吧！

有向无环图G(V,E)的一个路径覆盖是指一个路径集合P，满足图中的每点属于且仅属于集合中的一条路径。

由于出题者不知道如何上传图片，就用数字来解释吧。

考虑一个有5个顶点的有向无环图，有6条路径为

1->3

2->3

2->5

3->4

3->5

4->5

那么最少路径覆盖|P|min=2，

有三种方案：

A.{1->3->4->5, 2}

B.{2->3->4->5, 1}

C.{1->3->4, 2->5}

现在，聪明的你应该知道了你的任务就是：

给你一个有向无环图G=(V,E)，求一个包含路径数最少的路径覆盖P。

輸入說明：

输入测试数据有多笔。

每组测资的第一行是两个数n和m，分别代表有向无环图的节点数和接下来的信息数。

接下来m行，每行都是一对数x和y，表示存在一条路使得x可以不通过其他节点而直接到达y，即x->y。

当 x=y=0 时，代表输入结束，不必对这笔输入输出任何字符。

輸出說明：

对于每组测资，输出这个有向无环图的最少路径覆盖数。

範例輸入：

範例輸出：

提示：

由于为了保证有向图无环且无重边，所以测资很难生。

所以测资保证有

1<=n<=100

0<=m<=n*(n+1)/2

且有向图中一定没有环，也没有重边。

但是还希望大家将程序写得有效率一点，让它可以过掉n=1000的测资吧！

这对大家一定是一个挑战！

出處：

图论经典 (管理：liouzhou_101)

作法轉載自 http://www.cppblog.com/jericho/archive/2011/03/05/141175.aspx

题意：
有向无环图中，需要多少条简单路可以覆盖整个图。

建模：
构造二分图。把原图的每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图的边(i, i)，连接(Xi, Yj)，值为1，然后把二分图最大匹配模型转化为网络留模型，求最大流。

分析：

对于一个路径覆盖，有如下性质：

1、每个顶点属于且只属于一个路径。
2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。

所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 - 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。

注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。

/**********************************************************************************/
/* Problem: d739 "最少路径覆盖" from 图论经典                          */
/* Language: C                                                                   */
/* Result: AC (22ms, 384KB) on ZeroJudge                                         */
/* Author: morris1028 at 2011-08-27 15:12:02                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MaxV 10000000
#define MinV 0
int Map[202][202];
int max_flow(int st, int ed, int n) {
   int maxflow = 0, tn , tw;
   int pre[202], V[202], a, b;
   int Q[100001], Qt;
   while(1) {
       int Used[201] = {};
       for(a = 0; a <= n; a++)   V[a] = MinV;
       V[st] = MaxV;
       Qt = 0, Q[0] = st, pre[st] = st;
       for(a = 0; a <= Qt; a++) {
           tn = Q[a], Used[tn] = 0;
           for(b = 1; b <= n; b++) {
               tw = (V[tn] < Map[tn][b]) ? V[tn] : Map[tn][b];
               if(tw > V[b]) {
                   V[b] = tw, pre[b] = tn;
                   if(Used[b] == 0)
                       Q[++Qt] = b, Used[b] = 1;
               }
           }
       }
       if(V[ed] == 0) break;
       maxflow += V[ed];
       for(a = ed; a != st; a = pre[a]) {
           Map[pre[a]][a] -= V[ed], Map[a][pre[a]] += V[ed];
       }
   }
   return maxflow;
}
main() {
   int n, m, x, y, a;
   while(scanf("%d %d", &n, &m) == 2) {
       if(n == 0 && m == 0)
           break;
       memset(Map, 0, sizeof(Map));
       int st = 0, ed = 2*n+1;
       for(a = 0; a < m; a++)
           scanf("%d %d", &x, &y), Map[x][n+y] = 1;
       for(a = 1; a <= n; a++)
           Map[st][a] = 1, Map[a+n][ed] = 1;
       printf("%d\n", n-max_flow(st, ed, 2*n+1));
   }
   return 0;
}

我要檢舉

#d739#最少路径覆盖

台長： Morris

您可能對以下文章有興趣

[ZJ][離線、BIT、離散化] a580. 輻射擴散

[ZJ][多邊形面積] d546. 3. 剪多邊形（molding）

d903. 數學達人

[a462] Beats of the Angel

人氣(1,191) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:a194. 死亡 FLAG
此分類上一篇:a229. 括號匹配問題

回應(0)