思路
首先要提一下的就是，这道题有很多种做法，比如说有二分图匹配、并查集、贪心、搜索等等。出于时间原因，我这里只写二分图匹配和并查集写法。
一、二分图匹配（匈牙利算法）
这道题的这种做法思路比较难想（但也没有那么困难）。比较容易想到的就是把每个物品的两个属性作为两边的点，然后搞二分图匹配。但是这样做并不好做（我不清楚这样该怎么做）。
那我们可以考虑换一种思维方式。
我们可以对装置和其属性分别建点，然后从每个属性值分别向它所属的装备连有向边（注意一定是有向边，否则会出现全部都可以匹配的错误结果），然后在建好的二分图上跑匈牙利算法。
在统计答案时，我们从1开始依次枚举属性值，然后跑匈牙利，判断是否能够匹配。只要出现第一个不能匹配的情况，终止枚举，因为属性值必须要求连续。二分图匹配的主要思路就这些，如果不能理解，
可以多举几个例子分析一下，就很好懂了（这里因为我懒，就不提供分析了）。
最后就是一个小优化。由于每次跑匈牙利的时候都要清空vis数组，每次都清空会导致时间复杂度上升（不过好像也能过，我没试过）。因此我们可以将vis数组定义为int类型，再使用一个时间戳tot，就是
相当于每次把表示是否匹配的0,1换成了tot-1和tot。这样不会对程序造成影响，而且可以小幅压缩时间。
Code
#include#include#include#include#include#define MAXN 1000009int n, lk[MAXN], res;//lk[i]=j 表示第i个点与第j个点匹配int head[MAXN], cnt;int vis[MAXN], tot;//tot是时间戳struct node{ int nxt, to;} edge[MAXN <<1];inline void add_edge(int x,int y){ ++cnt; edge[cnt].nxt = head[x]; edge[cnt].to = y; head[x] = cnt; return;}//建图int DFS(int k){ if(vis[k]==tot) return 0;//若已经被匹配过且没有其他方案，返回 0 vis[k] = tot;//打上时间戳标记 for (int i = head[k]; i;i=edge[i].nxt){//遍历图 int v = edge[i].to; if(lk[v]==0||DFS(lk[v])){//若当前点没有被匹配过或者已匹配的点有其他方案可以选择，即有增广路，改变方案 lk[v] = k;//将v与k匹配 return 1;//此时一定可以匹配，返回1 } } return 0;}int main(){ scanf("%d", for (int i = 1; i <= n;++i){ int u = 0, v = 0; scanf("%d%d", add_edge(u, i);//从两个属性值向武器编号连边 add_edge(v, i); } for (int i = 1; i <= 10000;++i){ ++tot;//时间戳 if(DFS(i)) ++res;//尝试匹配，若可行，累加答案 else break;//否则直接结束循环 } printf("%d\n", res); return 0;}
二、并查集做法
并查集做法的时间效率比二分图差不了多少，但是同样不太好理解。
对于每个数据，我们在每个武器的属性值之间连边，这样到最后会出现一些连通块。这些连通块存在的形式有2种，一种是树（不是环），另一种是环。
对于呈树的状态的连通块，对于此题，即一定存在一种情况，使得只有一个点不被取到。而面对最大连续的要求，很明显去取不到的那个点一定是当前连通块中权值最大的那个点。
对于呈环的形态的连通块，很明显当前环上所有的点全部都能被取到。
那么我们就可以在合并时使用flag数组来维护这个性质。在每次读入后，在每个武器的两个属性值之间连边。
然后就是一种情况是合并这两个点所在的连通块（注意是要把权值小的连通块合并到大的连通块里面），然后把权值小的连通块的flag赋值为1。
如果不是上述情况（比如这两个点已经在一个连通块里了），那么我们就让这个连通块的顶点（即根节点）的flag赋值为1。
这样做的话，对于一个大小为m的连通块，若由恰好m-1条边构成（即为树），可以保证最大点的flag为0；若由大于等于m条边构成（即为环），可以保证所有点的flag均为1。这样最后只要按照权值从小
到大遍历flag数组，和匈牙利算法类似得出结果（同样证明例子我就不写了，我有点懒）。
Code
#include#include#include#include#include#define MAXN 1000009int n, f[MAXN], res;int flag[MAXN];inline int get_father(int k){ return k == f[k] ? k : f[k] = get_father(f[k]);}//路径压缩的并查集写法inline void _init(void){ for (int i = 1; i <= n + 1; ++i) f[i] = i; return;}//初始化函数inline void _swap(int x = y, y = tmp; return;}//交换两个变量的值int main(){ scanf("%d", _init(); for (int i = 1; i <= n;++i){ int u = 0, v = 0; scanf("%d%d", u = get_father(u), v = get_father(v); if(u==v) flag[u] = 1;//若是同一个点，flag=1 else{//尝试合并 if(u>v) _swap(u, v);//要保证u