| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 6275 | Accepted: 3756 |
Description
Input
Output
Sample Input
2 4 3 3 4 1 3 2 3 3 3 1 3 1 2 2 3
Sample Output
2 1
Source
最小路径覆盖问题
首先说下最小路径覆盖和最小边覆盖的区别吧：
最小边覆盖：设图G=(V,E)，求一个元素个数最少的边集合F，使G中任意顶点都至少是F中某条边的端点。做法是利用：最大匹配+最小边覆盖=顶点数
最小路径覆盖：在一个有向图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）。有向无环图的中的做法是：根据原图构造二分图，构造方法是将每个顶点一分为二，即将顶点i分为i1和i2，若原图中存在一条从i到j的有向边，则在新二分图中从i1到j2边接一条边；接下来利用：二分图中最大匹配+原图最小路径覆盖=原图顶点数
这道题中只要先根据所给图构造二分图，然后在二分图中套用匈牙利算法求出最大匹配，再利用上式求解即可
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<vector> 5 #define MAX_V 250 6 7 using namespace std; 8 9 int V,E; 10 int match[MAX_V]; //所匹配的顶点 11 bool used[MAX_V]; //DFS中用到 的访问标记 12 vector<int> G[MAX_V]; //图的邻接表表示 13 14 //向图中增加一条边接u和v的边 15 void add_edge(int u,int v) 16 { 17 G[u].push_back(v); 18 G[v].push_back(u); 19 } 20 21 //通过DFS寻找增广路 22 bool dfs(int v) 23 { 24 used[v]=true; 25 26 for(int i=0;i<G[v].size();i++) 27 { 28 int u=G[v][i],w=match[u]; 29 if(w<0||(!used[w]&&dfs(w))) 30 { 31 match[v]=u; 32 match[u]=v; 33 return true; 34 } 35 } 36 37 return false; 38 } 39 40 //求解二分图的最大匹配 41 int bipartite_matching() 42 { 43 int res=0; 44 45 memset(match,-1,sizeof(match)); 46 47 for(int v=1;v<=V;v++) 48 { 49 if(match[v]<0) 50 { 51 memset(used,false,sizeof(used)); 52 if(dfs(v)) 53 res++; 54 } 55 } 56 57 return res; 58 } 59 60 int main() 61 { 62 int kase; 63 64 scanf("%d",&kase); 65 66 while(kase--) 67 { 68 for(int i=1;i<=2*V;i++) 69 G[i].clear(); 70 71 scanf("%d %d",&V,&E); 72 73 int a,b; 74 for(int i=0;i<E;i++) 75 { 76 scanf("%d %d",&a,&b); 77 add_edge(a,V+b); 78 } 79 80 printf("%d\n",V-bipartite_matching()); 81 } 82 83 return 0; 84 }
原文：http://www.cnblogs.com/lzj-0218/p/3567670.html
