POJ1325

题目大意：

有两台机器(A,B),分别有(n,m)种不同模式，有(k)个任务，第(i)个任务在(A)上需要模式(a_i)，在(B)上需要模式(b_i)，要完成两台机器最少转化多少次模式？

贪心地考虑如果我们决定在某一时刻把机器(A)调为(a_i)，那么一定把所有在(A)上需要模式(a_i)的任务都解决掉是最优的

如果我们把(A,B)的每个模式看作一个节点，每个任务看作连接(a_i,b_i)的一条边，那么任意一个节点可以覆盖所有与之相连的边

我们的任务是需要最少的节点覆盖所有的边

所以是裸的二分图最小点覆盖

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
	inline int read()
	{
		int x=0;char ch,f=1;
		for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
		if(ch=='-') f=0,ch=getchar();
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
		return f?x:-x;
	}
	const int N=1e4+10;
	int n,m,k;
	struct node
	{
		int id,x,y;
	}d[N];
	int f[N],ret;
	bool vis[N];
	int head[N],cnt;
	struct point
	{
		int nxt,to;
		point(){}
		point(const int &nxt,const int &to):nxt(nxt),to(to){}
	}a[N<<2];
	inline void link(int x,int y)
	{
		a[++cnt]=point(head[x],y);head[x]=cnt;
		a[++cnt]=point(head[y],x);head[y]=cnt;
	}
	inline bool find(int x)
	{
		for(int i=head[x];i;i=a[i].nxt)
		{
			int t=a[i].to;
			if(vis[t]) continue;
			vis[t]=1;
			if(!f[t]||find(f[t]))
			{
				f[t]=x;
				return 1;
			}
		}
		return 0;
	}
	inline void main()
	{
		while("haku")
		{
			n=read();
			if(!n) break;
			m=read(),k=read();
			memset(head,0,sizeof(head));
			memset(f,0,sizeof(f));
			cnt=ret=0;
			for(int i=1;i<=k;++i)
			{
				d[i].id=read(),d[i].x=read(),d[i].y=read();
				if(!d[i].x||!d[i].y) continue;
				link(d[i].x,d[i].y+n);
			}
			for(int i=1;i<=n;++i)
			{
				memset(vis,0,sizeof(vis));
				if(find(i)) ++ret;
			}
			printf("%lld
",ret);
		}
	}
}
signed main()
{
	red::main();
return 0;
}