题意
给出一个DAG（有向，没有环的图），现在要你选出尽可能少的几条路径，使得只要把你选出来的路径都走了一遍，就可以保证你已经走过的图中的每一个节点。注意，路径与路径之间，可以有公共点（即允许路径相交）。
思路
典型的“最小路径覆盖”问题。在这里直接给出此类问题的解法：
有向无环图最小不相交路径覆盖
定义：用最少的不相交路径覆盖所有顶点。
定理：把原图中的每个点V拆成Vx和Vy，如果有一条有向边A->B，那么就加边Ax-By。这样就得到了一个二分图，最小路径覆盖=原图的节点数-新图最大匹配。
简单证明：一开始每个点都独立的为一条路径，总共有n条不相交路径。我们每次在二分图里加一条边就相当于把两条路径合成了一条路径，因为路径之间不能有公共点，所以加的边之间也不能有公共点，这就是匹配的定义。所以有：最小路径覆盖=原图的节点数-新图最大匹配。
有向无环图最小可相交路径覆盖
定义：用最小的可相交路径覆盖所有顶点。
算法：先用floyd求出原图的传递闭包，即如果a到b有路，那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。
所谓传递闭包(Transitive Closure)就是指把原图里面所有能直接间接联通的点之间都给连上边（如果有联通的方向限制，这个方向也要保留）之后形成的图，也就是说只要在传递闭包中存在A->B，就一定可以在原图中找到一条从A到B的路径。求传递闭包使用Warshall算法，最简单的实现就是借助邻接矩阵了（下图直接截自离散数学课件）：
代码
以下实现使用了Hopcraft-Karp算法和Warshall算法。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; #pragma mark - Hopcroft-Karp Algorithm for BiGraph Matching (BGM_HK) const int MAXN = 1050; const int INF = 0x3f3f3f3f; struct Node{ vector<int> to; } X[MAXN],Y[MAXN];//index starts from 0 int nx,ny;//the number of nodes in the LHS(aka. X) as nx;RHS(aka. Y) as ny int dis; int first[MAXN]; int matchX[MAXN],matchY[MAXN];//x is matched with matchX[x];y is matched with matchY[y] int disX[MAXN],disY[MAXN]; bool ap_vis[MAXN];//vis marking array for augment path searching void init(){ for (int i = 0; i < MAXN; i++) { X[i].to.clear(); Y[i].to.clear(); } memset(first, -1, sizeof(first)); memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); } bool hk_bfs(){ queue<int> que; dis = INF;//records currently the smallest distance(length of the augmented path) memset(disX, -1, sizeof(disX));//reset disX and disY array to the status indicating that no match was made memset(disY, -1, sizeof(disY)); for (int i = 1; i <= nx; i++) { //iterate the LHS and find any available not-matched nodes if (matchX[i] == -1) { //if this node is not matched,add this node into the queue que.push(i); //the distance(length of the augmented path) should be zero for a bold, unmatched point disX[i] = 0; } } while (!que.empty()) { int u = que.front();//"current node" que.pop(); if (disX[u] > dis) { //if the augmented path derived from u is larger than someone we had examined,we don't need to examine this point anymore break; } for (int i = 0; i < X[u].to.size(); i++) { //iterate the nodes connected with current node (all connected nodes are,certainally, belongs to RHS) int v = X[u].to[i]; if (disY[v] == -1) { //if the distance data is void for the connected RHS node,we should update it disY[v] = disX[u] + 1; if (matchY[v] == -1) { //in this case, we can terminate the current augment path here dis = disY[v]; }else { //in this case,we try to go deeper on the existed augment path disX[matchY[v]] = disY[v] + 1; que.push(matchY[v]); } } } } return dis != INF;//if dis == INF, this means no longer augment path can be made } int ap_dfs(int u){ //the current LHS node is u for (int i = 0; i < X[u].to.size(); i++) { //iterate the connected RHS node v int v = X[u].to[i]; if (!ap_vis[v] && disY[v] == disX[u] + 1) { //we want to find a non-visited RHS node with the desired distance ap_vis[v] = true;//mark visited if (matchY[v] != -1 && disY[v] == dis) { //if this node has already matched and the distance is what we desired --> appropriate augment path exist, no need to advance continue; } if (matchY[v] == -1 || ap_dfs(matchY[v])) { //hangary algo. //if matchY = -1 --> augment path terminated，else go deeper matchX[u] = v; matchY[v] = u; return 1; } } } return 0; } int BGM_HK(){ int ans = 0; while (hk_bfs()) { memset(ap_vis, false, sizeof(ap_vis)); for (int i = 1; i <= nx; i++) { if (matchX[i] == -1) { ans += ap_dfs(i); } } } return ans; } #pragma mark - Warshall Algorithm for Transitive Closure (TC_W) int conmat[MAXN][MAXN]; int trans[2][MAXN][MAXN]; //index begins from 1 //should adopt trans[n%2] as transitive closure void TC_W(int n){ memcpy(trans[0], conmat, sizeof(conmat)); memcpy(trans[1], conmat, sizeof(conmat)); for (int d = 1; d <= n; d++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { trans[d%2][i][j] = trans[(d-1)%2][i][j] | (trans[(d-1)%2][i][d] & trans[(d-1)%2][d][j]); } } } } #pragma mark - int main(){ int n,m; while (scanf(" %d %d",&n,&m) != EOF) { if (n == 0 && m == 0) { break; } memset(conmat, 0, sizeof(conmat)); for (int i = 1; i <= m; i++) { int from,to; scanf(" %d %d",&from,&to); conmat[from][to] = 1; } TC_W(n); init(); nx = ny = n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) { continue; } if (trans[n%2][i][j]) { X[i].to.push_back(j); } } } int res = BGM_HK(); cout << nx - res << endl; } } |
