还是那个问题，二分图最大匹配的题不可能出裸题，一定会考察你建图的能力。
比如这道题，要达到“每个装备选择一个属性”这一目的，假设 x 有 a、b 两种属性，我们可以从 a、b 向 x 连一条有向边。
然后我们依次从 1 到 10001 判断能否完成匹配，假设如果 y 不能完成，那么从 1 到 y-1 就是完成了匹配的属性，答案就是 y-1。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 1000010 using namespace std; int n,vis[MAXN],net[MAXN]; int head[10010],nxt[MAXN*2],to[MAXN*2],tot,tim; void read(int &X){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} X=x*f; } void add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;} bool match(int u){ for(int i=head[u];i;i=nxt[i]) if(vis[to[i]]<tim){ vis[to[i]]=tim; if(!net[to[i]] || match(net[to[i]])){ net[to[i]]=u; return true; } } return false; } int main(){ read(n); for(int i=1,a,b;i<=n;i++){read(a);read(b);add(a,i);add(b,i);} for(int i=1;i<=10001;i++){ tim++; //用时间戳代替初始化vis数组，加快效率 if(!match(i)){ printf("%d ",i-1); return 0; } } return 0; }