本题介绍两种做法；

1 并查集

1 #include
2 using namespace std;
3 const int N=1000005;
4 int fa[N],n;
5 bool vis[N];
6
7 int getf(int a){
8 if(fa[a]==a) return a;
9 else return fa[a]=getf(fa[a]);
10 }
11
12 void mg(int a,int b){
13 int af=getf(a);
14 int bf=getf(b);
15 if(af==bf) vis[af]=true;
16 else{
17 if(af>n;
27 for(int i=1;i<=n+1;i++) fa[i]=i; 28 for(int i=1;i<=n;i++){ 29 int a,b; 30 cin>>a>>b;
31 mg(a,b);
32 }
33 for(int i=1;i<=n+1;i++){
34 if(!vis[i]){
35 cout<<i-1;
36 break;
37 }
38 }
39 return 0;
40 }

2 更普遍的做法，也是更容易想到的，用二分图匹配来做，

将每个武器的两个属性分别向武器连边，因为是连续攻击（即从1开始），我们从1开始匹配，直到不能匹配为止，此时就得到答案。

代码中T表示时间戳，代替了匈牙利算法每次的memset（vis）。

1 #include
2 using namespace std;
3 const int N=1000005;
4 int adj[N],lk[N],id[N];
5 int to[2*N],nex[2*N];
6 int T,tot;
7
8 int read()
9 {
10 int a=0,f=1; char c=getchar();
11 while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
12 while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
13 return a*f;
14 }
15
16 void ins(int x,int y){
17 nex[++tot]=adj[x];
18 adj[x]=tot;
19 to[tot]=y;
20 }
21
22 bool mt(int x){
23 for(int i=adj[x];i;i=nex[i]){
24 int v=to[i];
25 if(id[v]==T) continue;
26 id[v]=T;
27 if(!lk[v]||mt(lk[v])){
28 lk[v]=x;
29 return 1;
30 }
31 }
32 return 0;
33 }
34
35 int main(){
36 int n=read(),i,x,y;
37 for(i=1;i<=n;i++) {
38 x=read();y=read();
39 ins(x,i);ins(y,i);
40 }
41 for(i=1;i<=10000;i++){
42 T++;
43 if(!mt(i)) break;
44 }
45 cout<<i-1;
46 return 0;
47 }