poj1741，POJ 1325 Machine Schedule(zoj 1364) 最小覆蓋數

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=364

http://poj.org/problem?id=1325

題目大意：

給兩臺機器A和B，他們分別有n和m個工作模式，初始的時候都在Mode_0狀態上，切換工作模式的時候必須重啟機子。給你K個任務，第i個任務可以運行在A的mode_x上，B的mode_y上，求完成所有工作所需最少重啟次數。

思路：

poj1741？好吧，不會做。看了大神的思路：

對于任務(i,x,y),我們在A機mode_x與B機mode_y之間連一條邊.這樣,題目就變成了一個二分圖,我們的目的是完成所有任務,即覆蓋所有線段,題目要求選擇最少的點,使得每個線段至少有一個端點被選中(這個任務就被完成了),這就是最小點覆蓋模型,答案是這個二分圖的最大匹配.

#include<cstdio>
#include<cstring>
const int MAXN=200+10;
int head[MAXN],len,res[MAXN];
bool vis[MAXN];
struct edge
{int to,next;
}e[MAXN*MAXN];
void add(int from,int to)
{e[len].to=to;e[len].next=head[from];head[from]=len++;
}
bool find(int a)
{for(int i=head[a];i!=-1;i=e[i].next){int id=e[i].to;if(!vis[id]){vis[id]=true;if(res[id]==0 || find(res[id])){res[id]=a;return true;}}}return false;
}
int main()
{int n,m,k;while(scanf("%d",&n),n){		scanf("%d%d",&m,&k);memset(head,-1,sizeof(head));len=0;memset(res,0,sizeof(res));for(int i=1;i<=k;i++){int t,x,y;scanf("%d%d%d",&t,&x,&y);if( x != 0 && y != 0 )  // 初始態是0，默認完成。   add(x,y);}int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(find(i)) ans++;}printf("%d\n",ans);}return 0;
}