POJ 1325 点击打开链接
大致题意：
有两个机器A和B，A有n种模式，B有m种模式。现在有k个任务，每个任务可以由A机器的一个模式或者B机器的一个模式完成。例如（i，x，y）代表第i个任务可以在A机器的x模式下完成，也可以在B机器的y模式下完成。每个机器由一个模式转换成另一个模式需要花费1。现在问你，最少花费多少就可以将所有任务完成。
大致思路：
看题意，就知道这是一个二分图问题。可是不会建图。。。于是上网看了下别人的解题思路，就恍然大悟了(还是做题少)。。。
我们将每个任务的x和y进行连边，那么这条边就代表这个任务，这条边的两个端点都可以完成这个任务。。。然后都连完之后，寻求最小点覆盖就ok了。。
注意：两个机器的初始是0模式，所以输入有0的话，就不用连边了，因为我们不需要花费就可以直接完成。
代码：
#include<stdio.h> #include<iostream> #include<string.h> #include<vector> #include<queue> using namespace std; int pre[500]; int vis[500]; int ml[500],mr[500]; vector<int>V[500]; int n,m,k; int MaxMatch() { int sum=0; memset(vis,0,sizeof(vis)); memset(ml,-1,sizeof(ml)); memset(mr,-1,sizeof(mr)); for(int i=0;i<n;i++) { if(ml[i]==-1) { queue<int>Q; Q.push(i); pre[i]=-1; int flag=0; while(!Q.empty()&&!flag) { int st=Q.front(); Q.pop(); for(int j=0;j<V[st].size()&&!flag;j++) { int to=V[st][j]; if(vis[to]!=i) { vis[to]=i; Q.push(mr[to]); if(mr[to]>=0) { pre[mr[to]]=st; } else { flag=1; int d=st,e=to; while(d!=-1) { int temp=ml[d]; ml[d]=e; mr[e]=d; d=pre[d]; e=temp; } } } } } if(flag)sum++; } } return sum; } int main() { while(~scanf("%d",&n)&&n) { scanf("%d%d",&m,&k); for(int i=1;i<=500;i++)V[i].clear(); int i,x,y; for(int j=0;j<k;j++) { scanf("%d%d%d",&i,&x,&y); if(x*y) V[x].push_back(y); } printf("%d\n",MaxMatch()); } }
