poj 1325 Machine Schedule 二分匹配，可以用最大流來做

題目大意:機器調度問題,同一個任務可以在A,B兩台不同的機器上以不同的模式完成.機器的初始模式是mode_0,但從任何模式改變成另一個模式需要重啟機器.求完成所有工作所需最少重啟次數.

===================================================

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

但是這題我是用最大流水過的，可以增加一個超級源點和超級匯點分別和A，B機器的每個模式連一條邊權為一的邊，然後就是最大流了

注意起始時，機器都處在模式0！！
for(int i=0;i<k;i++)
{
   scanf("%d%d%d",&a,&b,&c);
   if(b*c!=0)
    map[b][c]=true;
}

下面是我的代碼

/*********
PRO: POJ 1325
TIT: Machine Schedule
DAT: 2013-08-16-15.50
AUT: UKean
EMA: huyocan@163.com
*********/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define  INF 1e9
using namespace std;
queue<int> que;//廣搜需要使用的隊列
int s,t;//源點和匯點
int flow[505][505];//殘流量
int p[505];//廣搜記錄路徑的父節點數組
int a[505];//路徑上的最小殘量
int cap[505][505];//容量網絡
int ans;//最大流
int read()
{
	int n,m,k;
	cin>>n;if(!n) return 0;
	cin>>m>>k;
	s=0;t=m+n+1;
	//1->n 是A n+1 ->n+m是B
	memset(cap,0,sizeof(cap));
	for(int i=0;i<k;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		if(b*c!=0)//記住初始狀態為0 0 所以只要b或c中有一個為0，那麼就不用把它存入圖中了
		cap[b+1][c+n+1]=1;
	}
	for(int i=1;i<=n;i++)
		cap[s][i]=1;
	for(int i=n+1;i<=n+m;i++)
		cap[i][t]=1;
	return 1;
}
int deal()//增廣路算法就不具體解釋了，詳細的解釋可以看我關於網絡流的第一篇博客
//   http://blog.csdn.net/hikean/article/details/9918093
{
	memset(flow,0,sizeof(flow));
	ans=0;
	while(1)
	{
		memset(a,0,sizeof(a));
		a[s]=INF;
		que.push(s);
		while(!que.empty())
		{
			int u=que.front();que.pop();
			for(int v=0;v<=t;v++)
			if(!a[v]&&cap[u][v]-flow[u][v]>0)
			{
				p[v]=u;
				que.push(v);
				a[v]=min(a[u],cap[u][v]-flow[u][v]);//路徑上的最小殘流量
			}
		}
		if(a[t]==0) break;
		for(int u=t;u!=s;u=p[u])
		{
			flow[p[u]][u]+=a[t];
			flow[u][p[u]]-=a[t];
		}
		ans+=a[t];
	}
	cout<<ans<<endl;
	return ans;
}
int main()
{
	while(read())
		deal();
	return 0;
}