二分图的最小顶点覆盖=二分图的最大匹配。
证明见
http://hi.baidu.com/keeponac/blog/item/1764bec86f820f8dc91768b7.html关键是分析题意：A,B两台机器，A有n个模式，B有m个模式，要完成K个任务，每个任务可以在A的i模式下完成，也可以在B的j模式下完成，求最少的模式切换次数，也就是用最少的模式覆盖所有的任务，将模式看成顶点，将任务看成边，也就是第k个任务可以由A的i模式覆盖或B的j模式覆盖，求最小顶点覆盖。由于任意一个任务不能用同一个机器的不同模式完成，且任务不分顺序，所以该图是二分图，分为两个模式集合。
//二分图的最小顶点覆盖等于二分图的最大匹配
#include <iostream>
using namespace std;
const int M=101;
bool g[M][M];
bool visit[M];
int link[M];
int m,n,k;
bool find(int i)
{
int j;
for(j=1;j<=m;j++)
{
if(g[i][j] && !visit[j])
{
visit[j]=true;
if(link[j]==0 || find(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
int main()
{
int i,j,t,res;
while(cin>>n,n)
{
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
res=0;
cin>>m>>k;
while(k--)
{
cin>>t>>i>>j;
g[i][j]=true;
}
for(i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
if(find(i))
res++;
}
cout<<res<<endl;
}
return 0;
}posted on 2011-09-13 16:00
大大木马 阅读(559)
评论(0) 编辑 收藏 引用