Luogu P1640 [SCOI2010]连续攻击游戏

思路

首先要提一下的就是，这道题有很多种做法，比如说有二分图匹配、并查集、贪心、搜索等等。出于时间原因，我这里只写二分图匹配和并查集写法。

一、二分图匹配（匈牙利算法）

这道题的这种做法思路比较难想（但也没有那么困难）。比较容易想到的就是把每个物品的两个属性作为两边的点，然后搞二分图匹配。但是这样做并不好做（我不清楚这样该怎么做）。

那我们可以考虑换一种思维方式。

我们可以对装置和其属性分别建点，然后从每个属性值分别向它所属的装备连有向边（注意一定是有向边，否则会出现全部都可以匹配的错误结果），然后在建好的二分图上跑匈牙利算法。

在统计答案时，我们从1开始依次枚举属性值，然后跑匈牙利，判断是否能够匹配。只要出现第一个不能匹配的情况，终止枚举，因为属性值必须要求连续。二分图匹配的主要思路就这些，如果不能理解，

可以多举几个例子分析一下，就很好懂了（这里因为我懒，就不提供分析了）。

最后就是一个小优化。由于每次跑匈牙利的时候都要清空vis数组，每次都清空会导致时间复杂度上升（不过好像也能过，我没试过）。因此我们可以将vis数组定义为int类型，再使用一个时间戳tot，就是

相当于每次把表示是否匹配的0,1换成了tot-1和tot。这样不会对程序造成影响，而且可以小幅压缩时间。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 1000009
int 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", &n);
    for (int i = 1; i <= n;++i){
        int u = 0, v = 0;
        scanf("%d%d", &u, &v);
        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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 1000009
int 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,int &y){
    int tmp = x;
    x = y, y = tmp;
    return;
}//交换两个变量的值
int main(){
    scanf("%d", &n);
    _init();
    for (int i = 1; i <= n;++i){
        int u = 0, v = 0;
        scanf("%d%d", &u, &v);
        u = get_father(u), v = get_father(v);
        if(u==v) flag[u] = 1;//若是同一个点，flag=1
        else{//尝试合并
            if(u>v) _swap(u, v);//要保证u<v
            if(!flag[u]) flag[u] = 1;//把权值小的赋值为1
            else flag[v] = 1;//否则再把权值大的赋值为1
            f[u] = v;//把u(权值小的)并到v(权值大的)上
        }
    }
    for (int i = 1; i <= n + 1; ++i){
        if(flag[i]==0){
            res = i - 1;//这里得出结果的方法和二分图写法类似
            break;
        }
    }
    printf("%d\n", res);
    return 0;
}

Luogu P1640 [SCOI2010]连续攻击游戏

原文：https://www.cnblogs.com/ShadowFlowhyc/p/13380741.html