【传送门：BZOJ1854】
简要题意：
给出n个武器，每个武器都有两个值，现在你要打boss，第一个回合你只能拿两个值中有一个值为1的武器，第二个回合只能用值为2的武器，以此类推，每个武器只能用一个回合，求出最多能打几个回合
题解：
二分图匹配，不过要用时间戳来节约时间，不然会T掉
参考代码：
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> using namespace std; struct node { int x,y,next; }a[2100000];int len,last[1100000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int chw[1100000]; int match[1100000]; bool findmuniu(int x,int i) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(chw[y]!=i) { chw[y]=i; if(match[y]==0||findmuniu(match[y],i)==true) { match[y]=x; return true; } } } return false; } int main() { int n; scanf("%d",&n); len=0;memset(last,0,sizeof(last)); int mmax=0; for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); ins(x,i); ins(y,i); mmax=max(max(mmax,x),y); } memset(chw,0,sizeof(chw)); memset(match,0,sizeof(match)); for(int i=1;i<=mmax;i++) { if(findmuniu(i,i)==false) { printf("%d ",i-1); return 0; } } printf("%d ",mmax); return 0; }