http://acm.split.hdu.edu.cn/showproblem.php?pid=1150
题目大意：有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式xi,如果它在机器B上运行，则机器B需要设置为模式yi。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。
这里有一个知识点：二分图的最小顶点覆盖数=最大匹配数。
判断是否为二分图：当且仅当G中无奇数长度的回路，一个无向图G=<V,E>是二分图
(用增广路经求二分图最大匹配。核心：寻找增广路)：
主要思路就是不断寻找增广路经，增加匹配的个数。给定一个二分图G，在G的一个子图M中，M的边集中任意两条边都不依附于同一个顶点，则称M是一个匹配。如果一个匹配中，图中的每个顶点都和图中的某条边相关联，则称此匹配为完全匹配。
增广路经：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属于M的边在P上交替出现，则称P为相对于M的一条增广路径。
a. P的路径长度必定为奇数，第一条边和最后一条边都不属于M.
b. P经过取反操作可以得到一个更大的匹配M。.
c. 当且仅当不存在相对于M的增广路经，M为G的最大匹配。
#include<iostream>
#include<cstring>
using namespace std;
int map[][];
int v[],p[];
int n,m,k; int Find(int x)
{
for(int i=; i<m; i++)
{
if(map[x][i]== && !v[i])
{
v[i]=;
if(p[i]==- || Find(p[i]))
{
p[i]=x;
return ;
}
}
}
return ;
} int main()
{
while(cin>>n && n)
{
cin>>m>>k;
int a,b,c;
int ans=;
memset(map,,sizeof(map));
memset(p,-,sizeof(p));
for(int i=; i<=k; i++)
{
cin>>a>>b>>c;
if(b && c)
map[b][c]=;
}
for(int i=; i<n; i++)
{
memset(v,,sizeof(v));
ans+=Find(i);
}
cout<<ans<<endl;
}
return ;
}