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;
}