題意： 兩臺機器，有 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[二分图匹配*最小点覆盖]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。