图论训练之十五

https://www.luogu.org/problem/P1640

好像每次二分图都用dinic不太好写

于是就学着写匈牙利算法

分析：

每件装备只能用一次，如果把攻击序列建成点，就是装备和攻击顺序的匹配。

比如属性值是3和5，那么这件装备要么在3位置要么在5位置被使用。

当然，按攻击顺序开始匹配，一旦匹配不成功，根据题意就必须中止。

还有，每次memset太慢了，用时间戳id。

code by wzxbeliever：

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ri register int
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=1010005;
const int maxval=10000;
struct node{
	int to,next;
}edg[maxn<<2];
int head[maxn],vis[maxn],match[maxn];
int n,cnt,id;
il void add(int u,int v){
	cnt++;
	edg[cnt].next=head[u];
	edg[cnt].to=v;
	head[u]=cnt;
	return;
}
il bool dfs(int u){
	for(ri i=head[u];i;i=edg[i].next){
		int to=edg[i].to;
		if(vis[to]-id){
			vis[to]=id;
		    if(!match[to]||dfs(match[to])){
		    	match[u]=to;match[to]=u;
		    	return true;
			}
		}
	}
	return false;
}
il int hungary(){
	int res=0;
	for(ri i=id=1;i<=maxval;id++,i++)
	if(dfs(i))res++;
	else break;
	return res;
}
int main(){
	scanf("%d",&n);
	for(ri i=1,x;i<=n;i++)
	for(ri j=1;j<=2;j++)
	scanf("%d",&x),add(x,i+maxval),add(i+maxval,x);
	printf("%d
",hungary());
	return 0;
}