POJ1325 Machine Schedule【二分图最小点覆盖】
题目链接:
http://poj.org/problem?id=1325
题目大意:
有两台机器A和B,机器A有N种不同的模式,编号为0~N-1。机器B有M种不同的模式,编号为0~M-1。
在一开始的时候,机器A和B都处于0模式。现在需要用两台机器来处理K项任务,任务编号为0~K-1。每
一项任务都可以在A或B的指定状态下完成。例如任务1可以在机器A的2模式下完成,也可以在机器B的4
模式下完成。对于第i想任务用(i,x,y)来表示第i项任务可以在机器A的x模式下或机器B的y模式下完成。
为了完成所有任务,不得一次次地切换机器的工作模式。而切换机器的工作模式只能通过重启机器来完
成。那么问题来了:最少需要重启多少次机器,能够完成这K项任务。
思路:
建立一个二分图,一边为机器A,另一边为机器B。一项任务既能在机器A的x模式或是机器B的y模式下完
成,则在二分图中建立一条边(x,y)。求最少的机器切换次数,就是求是否存在一个最小规模的点集,使
得所有的边都至少和这个点集中的一个点相关联,也就是求二分图最小点集覆盖。而二分图最小点覆盖等
于二分图最大匹配,直接用匈牙利算法就可以求出了。
AC代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 110; bool Map[MAXN][MAXN],Mask[MAXN]; int NX,NY; int cx[MAXN],cy[MAXN]; int FindPath(int u) { for(int i = 0; i < NY; ++i) { if(Map[u][i] && !Mask[i]) { Mask[i] = 1; if(cy[i] == -1 || FindPath(cy[i])) { cy[i] = u; cx[u] = i; return 1; } } } return 0; } int MaxMatch() { for(int i = 0; i < NX; ++i) cx[i] = -1; for(int i = 0; i < NY; ++i) cy[i] = -1; int res = 0; for(int i = 0; i < NX; ++i) { if(cx[i] == -1) { for(int j = 0; j < NY; ++j) Mask[j] = 0; res += FindPath(i); } } return res; } int main() { int N,M,K,a,u,v; while(~scanf("%d",&N) && N) { memset(Map,0,sizeof(Map)); scanf("%d%d",&M,&K); NX = N,NY = M; for(int i = 1; i <= K; ++i) { scanf("%d%d%d",&a,&u,&v); if(u*v != 0) Map[u][v] = 1; } printf("%d\n",MaxMatch()); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。