这道题当时有一瞬间想到是二分图匹配……因为我们必须保证每次攻击的前一次都是当前值-1，能想到是匹配，可是看到数据范围是10^6，当时就觉得的这不可能是二分图匹配。
不过这题还真是二分图匹配……
它的匹配方法不大一样，因为一个装备有两个属性，所以我们可以想到把每个装备都向它的两个属性值连边，之后我们考虑一下，对于一件装备，我们只能选取其中一种状态，不过在匹配到后来的时候可能有一种情况比它更优，也就是说，我们让这件装备匹配自己的另一个价值，并且用另一件装备去匹配当前的价值。（因为我们要求的是价值被匹配，所以我们只要保证每个价值都被匹配就行）之后我们就可以使这个价值成功的去被匹配到。这就是一个很标准的二分图匹配的模型了。
因为这道题要按照严格递增的顺序来匹配，而且边数过多，不能使用网络流，要使用匈牙利算法。从1开始枚举，每次如果匹配成功答案+1继续匹配，否则直接退出即可。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 1000005; const int N = 10005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to,from; }e[M<<1]; int n,pre[M],x,y,head[N],ans,ecnt; bool vis[N]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } bool dfs(int x) { if(vis[x]) return 0; vis[x] = 1; for(int i = head[x];i;i = e[i].next) { if(!pre[e[i].to] || dfs(pre[e[i].to])) { pre[e[i].to] = x; return 1; } } return 0; } int main() { n = read(); rep(i,1,n) x = read(),y = read(),add(x,i),add(y,i); rep(i,1,10000) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; else break; } printf("%d ",ans); return 0; }