【bzoj1854 Scoi2010】游戏（二分图匹配）

题目：

我是超链接

题解：

二分图匹配裸题

因为每种装备用一次，就把这两个装备连在上面做匹配呗

代码：

#include <cstdio>
#include <iostream>
using namespace std;
const int N=1e6+5;
int vis[N],belong[N],tot,point[N],nxt[N*4],v[N*4];
void addline(int x,int y)
{
	++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
}
bool find(int x,int k)
{
	for (int i=point[x];i;i=nxt[i])
	  if (vis[v[i]]!=k)
	  {
	  	vis[v[i]]=k;
	  	if (!belong[v[i]] || find(belong[v[i]],k))
	  	{
	  		belong[v[i]]=x;
	  		return true;
		}
	  }
    return false;
}
int main()
{
	int n,i,maxx=0;
	scanf("%d",&n);
	int x,y;
	for (i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		addline(x,i); addline(y,i);
		maxx=max(maxx,max(x,y));
	}
	for (i=1;i<=maxx;i++)
	  if (!find(i,i))
	  {
	  	printf("%d",i-1);
	  	return 0;
	  }
	printf("%d",maxx);
}