POJ 1325 Machine Schedule[二分图匹配*最小点覆盖]

题意： 两台机器，有 k 个工作，每个工作可以在 a 机器的 P 模式或在 b 机器的 q 模式下解决，两台机器初始状态为 0 模式，每台机器没变换一次模都要重启一次，

　　　 问至少重启多少次可以完成所有工作。

分析： 构图方式

          if(x*y!=0)

　　　　g[x][y]=1;

       求出最小点覆盖，即找到最少的点来覆盖所有的边。

 

View Code #include<stdio.h> #include<string.h> #define clr(x)memset(x,0,sizeof(x)) struct node {int to,next; }q[100000]; int head[102]; int tot; void add(int s,int u) {q[tot].to=u;q[tot].next=head[s];head[s]=tot++; } int link[102]; int v[102]; int find(int x) {int k,i;for(i=head[x];i;i=q[i].next){k=q[i].to;if(!v[k]){v[k]=1;if(link[k]==0||find(link[k])){link[k]=x;return 1;}}}return 0; } int main() {int tot,x,y,n,m,s,i,k;while(scanf("%d",&n),n){scanf("%d%d",&m,&k);tot=1;clr(link); clr(head);for(i=1;i<=k;i++){scanf("%*d%d%d",&x,&y);if(x*y!=0)add(x,y);}tot=0;for(i=1;i<n;i++){clr(v);if(find(i))tot++;}printf("%d\n",tot);}return 0; }

 

转载于:https://www.cnblogs.com/dream-wind/archive/2012/04/22/2464646.html

总结

以上是生活随笔为你收集整理的POJ 1325 Machine Schedule[二分图匹配*最小点覆盖]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。