首页 > 代码库 > 二分图最小点覆盖
二分图最小点覆盖
二分图模型中的最小顶点覆盖问题：在二分图G=(X,Y;E)中求取最小的顶点集V* ⊂ ｛X,Y｝,使得边 e ∈ E都至少有一个顶点 v ∈ V*相关联。
简单地说，最小点覆盖就是从图G的顶点中取最少的点组成一个集合，使得图中所有的边都与取出来的点相连。
有一定理：最小顶点覆盖问题与最大匹配问题等价。
题目：hdu1150
题目大意:
有两台机器A和B。A机器有N种不同的模式，B机器有M种不同的模式。每个任务都可以在一台机器上独立完成。如果它在机器A上运行，则机器A需要设置为模式xi；如果它在机器B上运行，则机器A需要设置为模式yi。每台机器 上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。求机器重启的最小次数。
解题思路：
X={机器A的集合}，Y={机器B的集合}，E={(i,j) | 任务K由机器A的i模式完成或者由机器B的j模式完成}，这样就构造了一个二分图。
这样构图以后，明显看出就是求最小点覆盖。
本题有个特殊的地方，就是0这个状态是初始状态，就是说这个状态是不需要代价的（在最小代价的情况下）。
求最大匹配我用的是Hopcroft-Karp算法，时间复杂度为O(m*n1/2)。而匈牙利算法（BFS版，DFS版）时间复杂度都是O(m*n)。
下面的是代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 8 const int N=1005,INF=0x3f3f3f3f; 9 int bmap[N][N],cx[N],cy[N],dx[N],dy[N];10 bool bmask[N];11 int nx,ny,dis,ans;12 bool searchpath()13 {14 queue<int> q;15 dis=INF;16 memset(dx,-1,sizeof(dx));17 memset(dy,-1,sizeof(dy));18 for(int i=1;i<=nx;i++)19 {20 if(cx[i]==-1){ q.push(i); dx[i]=0; }21 while(!q.empty())22 {23 int u=q.front(); q.pop();24 if(dx[u]>dis) break;25 for(int v=1;v<=ny;v++)26 {27 if(bmap[u][v]&&dy[v]==-1)28 {29 dy[v]= dx[u] + 1;30 if(cy[v]==-1) dis=dy[v];31 else32 {33 dx[cy[v]]= dy[v]+1;34 q.push(cy[v]);35 }36 }37 }38 }39 }40 return dis!=INF;41 }42 int findpath(int u)43 {44 for(int v=1;v<=ny;v++)45 {46 if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1)47 {48 bmask[v]=1;49 if(cy[v]!=-1&&dy[v]==dis) continue;50 if(cy[v]==-1||findpath(cy[v]))51 {52 cy[v]=u; cx[u]=v;53 return 1;54 }55 }56 }57 return 0;58 }59 void maxmatch()60 {61 ans=0;62 memset(cx,-1,sizeof(cx));63 memset(cy,-1,sizeof(cy));64 while(searchpath())65 {66 memset(bmask,0,sizeof(bmask));67 for(int i=1;i<=nx;i++)68 if(cx[i]==-1) ans+=findpath(i);69 }70 }71 void init()72 {73 memset(bmap,0,sizeof(bmap));74 }75 int main()76 {77 //freopen("test.txt","r",stdin);78 int m,i,j,k;79 while(scanf("%d",&nx)!=EOF)80 {81 if(!nx) break;82 scanf("%d%d",&ny,&m);83 init();84 while(m--)85 {86 scanf("%d%d%d",&i,&j,&k);87 if(j&&k) bmap[j][k]=1;88 }89 maxmatch();90 printf("%d\n",ans);91 }92 return 0;93 }
最小顶覆盖还有其他做法，不过和二分图无关。一种是贪心的做法，一种是树形DP。
我只贴出贪心版的代码（其实就是深搜）,其中也有最小支配集、最大独立集。
1 /*newpos[i]表示深度优先遍历序列的第i个点是哪个点， 2 now表示当前深度优先遍历序列已经有多少个点了。select[]用于 3 深度优先遍历的判重，p[i]表示点i的父节点的编号。对于greedy(), 4 s[i]为1表示第i个点被覆盖。se[i]表示点i属于要求的点集*/ 5 6 const int N = 1010; 7 int p[N], newpos[N] ; 8 bool select[N]; 9 int n ,m ,now ; 10 //深度优先遍历，得到深度优先遍历序列 11 void dfs(int x) 12 { 13 nespos[now++] = x; 14 int k; 15 for(k=head[x]; k!=-1; k=e[k].next) 16 { 17 if(!select[e[k].to]) 18 { 19 select[e[k].to]= 1; 20 p[e[k].to]=x; 21 dfs(e[k].to); 22 } 23 } 24 } 25 //最小支配集 26 int greedy1() 27 { 28 bool s[N]={0}; 29 bool se[N]={0}; 30 int ans=0; 31 int i; 32 for(i=n-1; i>=0; i--) 33 { 34 int t=newpos[i]; 35 if(!s[t]) 36 { 37 if(!se[p[t]]) 38 { 39 se[p[t]]=1; 40 ans++; 41 } 42 s[t] = 1; 43 s[p[t]] = 1; 44 s[p[p[t]]] = 1; 45 } 46 } 47 return ans; 48 } 49 //最小点覆盖 50 int greedy2() 51 { 52 bool s[N]={0}; 53 bool se[N]={0}; 54 int ans=0; 55 int i; 56 for(i=n-1; i>=1; i--) 57 { 58 int t=newpos[i]; 59 if(!s[t]&&!s[p[t]]) 60 { 61 se[p[t]]=1; 62 ans++; 63 s[t] = 1; 64 s[p[t]] = 1; 65 } 66 } 67 return ans; 68 } 69 //最大独立集 70 int greedy3() 71 { 72 bool s[N]={0}; 73 bool se[N]={0}; 74 int ans=0; 75 int i; 76 for(i=n-1; i>=0; i--) 77 { 78 int t=newpos[i]; 79 if(!s[t]) 80 { 81 se[t]=1; 82 ans++; 83 s[t] = 1; 84 s[p[t]] = 1; 85 } 86 } 87 return ans; 88 } 89 90 int main() 91 { 92 /* 读入图*/ 93 memset(select, 0, sizeof(select)); 94 now=0; 95 select[1]=1; 96 p[1]=1; 97 dfs(1); 98 printf("%d\n",greedy()); 99 return 0;100 }
二分图最小点覆盖
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。