很早之前写的题了，发现没有更博，想了想，更一发出来。

Orz ljss

这是冬令营上的例题...之后，我推出来了一种时间复杂度没有问题，空间复杂度没有问题的方法，额(⊙o⊙)…和给出的正解不同，但是能AC

分析：

正解是什么我忘了，我还是讲一下我自己的方法吧...

首先，这是一个并查集的题...但是，我没有用并查集...之后呢，我当时并不会二分图，也不会匈牙利...之后，我根据臆测...莫名其妙的想到了用二分图+匈牙利算法的方法解决这道题...（这也可以？！）

我们可以这样考虑一下，每个武器有两个属性，那么我们可以连两条边，属性和对应的武器号，顺便，开一个桶处理出每一个属性有多少把武器。

之后呢，枚举答案，对，枚举答案！

枚举答案从1到最大值，判断一下桶中的个数是否为0，如果为0，输出i-1，并且退出程序

如果桶中个数为1，那么说明，如果想要到达这个答案，我们必须使用这把武器的这个属性，那么，我们在对应武器的另一个属性的桶中减去这把武器，即：num[a[i^1]]--;

并且，将这把武器打上标记，下次使用的时候，不能继续使用。

在a[i^1]<a[i]的前提下：

如果num[a[i^1]]减成0，那么答案为i-1，并且退出程序。

如果num[a[i^1]]大于1，那么继续枚举答案。

如果num[a[i^1]]恰好等于1，那么我们递归的继续处理a[i^1]这个属性，处理方法同上。

（手动模拟匈牙利算法，捂脸！！！鬼知道我当时怎么想出来的！！！）

时间复杂度：（可过）

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define N 1000005#define M 10005int n;int a[N<<1],num[M],u;bool vis[N<<1];struct node{ int to,next;}e[N<<1];int head[M],cnt;void add(int x,int y){ e[cnt].to=y; e[cnt].next=head[x]; head[x]=cnt++; return ;}bool work(int x){ if(num[x]==0&&u>=x)return 0; if(num[x]==1&&u>=x) { for(int i=head[x];i!=-1;i=e[i].next) { int to1=e[i].to; if(!vis[to1]) { num[a[to1^1]]--; vis[to1]=vis[to1^1]=1; if(!work(a[to1^1])) { return 0; }else { return 1; } } } } return 1;}int main(){ memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=0;i<(n<<1);i++) { scanf("%d",&a[i]); num[a[i]]++; add(a[i],i); } int i; for(i=1;i