开始以为是求最小支配集,结果给我胡乱AC了。后来感觉不太对,去搜解题报告才知道是最小路径覆盖。
【建模分析】
对于一个路径覆盖,有如下性质:
1、每个顶点属于且只属于一个路径。
2、路径上除终点外,从每个顶点出发只有一条边指向路径上的另一顶点。
所以我们可以把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图模型。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。如果匹配数为0,那么显然路径数=顶点数。每增加一条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 – 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。
注意,此建模方法求最小路径覆盖仅适用于有向无环图,如果有环或是无向图,那么有可能求出的一些环覆盖,而不是路径覆盖。
推荐一个不错的博客:
http://www.byvoid.com/blog/lpf24-3/
CODE:
#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> using namespace std; #define MAXN 130 #define MAXM 20010 int G[MAXN][MAXN]; int xlink[MAXN]; int ylink[MAXN]; bool vis[MAXN]; int nx, ny, m; inline void init() { memset(G, 0, sizeof(G)); memset(xlink, -1, sizeof(xlink)); memset(ylink, -1, sizeof(ylink)); } bool ED(int u) { for(int v = 1; v <= ny; v++) if(G[u][v]) { if(!vis[v]) { vis[v] = 1; if(ylink[v] == -1 || ED(ylink[v])) { xlink[u] = v; ylink[v] = u; return true; } } } return false; } void MaxMatch() { int ans = 0; for(int i = 1; i <= nx; i++) { if(xlink[i] == -1) { memset(vis, 0, sizeof(vis)); ans += ED(i); } } printf("%d\n", nx-ans); } int main() { int T; scanf("%d", &T); while(T--) { init(); scanf("%d%d", &nx, &m); ny = nx; while(m--) { int u, v; scanf("%d%d", &u, &v); G[u][v] = 1; } MaxMatch(); } return 0; }