CSU-ACM2018暑期训练11-并查集&最小生成树 - Virtual Judge

A - The Suspects

题意

有n个人，m个信息，每个信息表示k个人曾经接触过。现在已知编号为0的人患有非典，问共有几个人被怀疑可能会感染。

思路

简单并查集，维护一下每个集合的大小即可。

代码

#include <cstdio>

const int MAXN = 3e4+10;

int n, m;
int fa[MAXN];
int cnt[MAXN];

void makeFa() {
    for(int i=0; i<n; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
}

int find(int x) {
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx==fy) return false;
    cnt[fx] += cnt[fy];
    fa[fy] = fx;
    return true;
}

int main() {
    while(scanf("%d%d", &n, &m)==2 && (n||m)) {
        makeFa();
        for(int i=0; i<m; i++) {
            int k, a;
            scanf("%d%d", &k, &a);
            for(int j=1; j<k; j++) {
                int b;
                scanf("%d", &b);
                merge(a, b);
            }
        }
        printf("%d\n", cnt[find(0)]);
    }
    return 0;
}

B - A Bug's Life

题意

教授认为有一种虫子只与性别不同虫子交互，现在给你若干组虫子交互的记录，问教授的假设是否错误。

思路

简单带权并查集。两只虫子的性别关系可以通过同一集合中的虫子的性别关系推导出。维护每只虫子与其父节点的关系即可。

代码

#include <cstdio>

const int MAXN = 3e4+10;

int n, m;
int fa[MAXN];
int same[MAXN];

void makeFa() {
    for(int i=1; i<=n; i++) {
        fa[i] = i;
        same[i] = true;
    }
}

int find(int x) {
    if(x==fa[x]) return x;
    int fx = find(fa[x]);
    same[x] = same[x]==same[fa[x]];
    fa[x] = fx;
    return fx;
}

bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx==fy) return same[x]!=same[y];
    same[fy] = same[x]!=same[y];
    fa[fy] = fx;
    return true;
}

int main() {
    int T;
    scanf("%d", &T);
    for(int cs=1; cs<=T; cs++) {
        scanf("%d%d", &n, &m);
        makeFa();
        bool flag = true;
        for(int i=0; i<m; i++) {
            int a,b;
            scanf("%d%d", &a, &b);
            flag = flag && merge(a, b);
        }
        printf("Scenario #%d:\n%s bugs found!\n\n", cs, flag?"No suspicious":"Suspicious");
    }
    return 0;
}

C - 食物链

题意

中文题，题意也比较明确。

思路

本题的关键在于，用一种合理的方法来确定相关的鱼的关系。

显然，对于任意相关的两条鱼A、B，他们的关系只能有三种：

• A与B是同类
• A吃B
• B吃A

那么我们考虑三条鱼的情况。假如我们已知A与B的关系和B与C的关系，我们能否快速得出A与C的关系呢？

这里我们使用一个技巧，将两条鱼的关系抽象为数字：

那么进行关系运算的方式就是：relation(a, c) = (relation(a, b) + relation(b, c)) % 3

举个例子，假如A吃B，B吃C，则relation(A, B)=1，relation(B, C)=1。经过计算，relation(A, C)=(relation(A, B)+relation(B, C))%3=2，说明C吃A，与我们的预期是相同的。

在实现的时候，我们定义一个relation数组，relation[x]表示上面所说的relation(fa[x], x)，然后在find和merge的过程中维护这个relation数组就好了。

另外提一下，只有当输入的X和Y已经在同一个集合中了，这句话才有可能是假话。也就是说，当且仅当find(X)==find(Y)且relation(X, Y)!=输入的关系时，这句话是假话，其中relation(X, Y) = (relation[X]+3-relation[Y])%3。

代码

#include <cstdio>
using namespace std;

const int MAXN = 5e4+10;
int n, k;
int fa[MAXN];
int relation[MAXN];

void makeFa() {
    for(int i=1; i<=n; i++) {
        fa[i] = i;
        relation[i] = 0;
    }
}

int find(int x) {
    if(x==fa[x]) return x;
    int fx = find(fa[x]);
    relation[x] = (relation[x]+relation[fa[x]])%3;
    fa[x] = fx;
    return fx;
}

bool merge(int x, int y, int r) {
    int fx = find(x), fy = find(y);
    if(fx==fy) return (relation[x]-relation[y]+3)%3==r;
    relation[fx] = (-relation[x]+r+relation[y]+3)%3;
    fa[fx] = fy;
    return true;
}

int main() {
    scanf("%d%d", &n, &k);
    makeFa();
    int ans = 0;
    for(int i=0; i<k; i++) {
        int d,x,y;
        scanf("%d%d%d", &d, &x, &y);
        if(x>n || y>n) {
            ans++;
            continue;
        }
        if(!merge(x, y, d-1))
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}

D - X-Plosives

题意

有n种化合物，每种化合物由两种元素组成。当几种的化合物数量等于他们所含不同元素的数量时，就会发生爆炸。现在依次给出化合物的组成，当新的化合物与之前的化合物放在一起会发生爆炸时，就不能允许这个化合物放进来。

输出拒绝的次数。

思路

把元素看成点，化合物看成边，每次新的化合物进来当成连一条边。如果图中没有环，则每个连通分量是一棵树，其边数等于点数减1，不可能存在爆炸的情况；如果图中有环，则这个环上点数等于边数，就会爆炸。

使用并查集连边，如果要连的两个点在同一集合中，则答案加1。

代码

#include <cstdio>

const int MAXN = 1e5+10;

int fa[MAXN];

int find(int x) {
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx==fy) return false;
    fa[fx] = fy;
    return true;
}

void makeFa() {
    for(int i=1; i<MAXN; i++) {
        fa[i] = i;
    }
}

int main() {
    int a,b;
    while(scanf("%d", &a)==1) {
        makeFa();
        int ans = 0;
        while(a!=-1) {
            scanf("%d", &b);
            if(!merge(a, b))
                ans++;
            scanf("%d", &a);
        }
        printf("%d\n", ans);
    }
    return 0;
}

E - Almost Union-Find

题意

初始时，一共有n个元素的组合。

给出三个操作：

• 1 p q：合并p, q所在的集合
• 2 p q：把p移动到q所在的集合
• 3 p：输出p所在的集合的元素的个数和元素之和

思路

这道题除了有合并和查询操作以外，还增加了移动操作。如果直接使用元素本身作为结点下标的话，移动它会影响所有以它为根结点的子树结点。

解决方法是不使用元素本身作为结点下标（除了一开始）。每次需要移动的时候，给该元素分配一个新的结点下标，然后维护它之前所在集合的大小和元素和，再合并新的结点到目标集合中。

代码

#include <cstdio>

const int MAXN = 200010;
int n, m;
int fa[MAXN], cnt[MAXN], sum[MAXN], id[MAXN], idx;

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        cnt[fy] += cnt[fx];
        sum[fy] += sum[fx];
        fa[fx] = fy;
    }
}

void move(int item, int set) {
    int fi = find(id[item]), fs = find(set);
    if (fi != fs) {
        cnt[fs]++;
        cnt[fi]--;
        sum[fs] += item;
        sum[fi] -= item;
        id[item] = ++idx;
        fa[idx] = fs;
    }
}

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++) {
            fa[i] = sum[i] = id[i] = i;
            cnt[i] = 1;
        }
        idx = n;
        while (m--) {
            int op;
            scanf("%d", &op);
            if (op == 1) {
                int a, b;
                scanf("%d%d", &a, &b);
                merge(id[a], id[b]);
            }
            else if (op == 2) {
                int a, b;
                scanf("%d%d", &a, &b);
                move(a, id[b]);
            }
            else {
                int a;
                scanf("%d", &a);
                int fx = find(id[a]);
                printf("%d %d\n", cnt[fx], sum[fx]);
            }
        }
    }
    return 0;
}

F - True Liars

题意

一个岛上有神与恶魔两个种族，神会说真话，恶魔会说假话。已知神与恶魔的个数，但不知道具体个人是属于哪个。

现在有n条信息，每条信息的含义是：x说y是神或不是神。

问能否确定哪些人是神。

思路

题目可以转化为，输入为“yes”说明两人是同类的，输入为“no”说明两人是不同类的。

我们最终把这一群人分成若干个大集合，每个大集合中又分为两个小集合，分别是好人和坏人，只是我们不知道哪个是好人集合，哪个是坏人集合。

因为题目已经告诉好人和坏人的个数，所以我们从这若干个大集合中每个集合挑出一个小集合，使这些小集合的大小之和等于好人数目，判断这样的情况有多少种，如果是一种，则可以确定哪些是好人哪些是坏人。

需要用到动态规划（背包）。

设数组dp[MAXP*2][MAXP]，dp[i][j]代表到第i个大集合时，好人数为j的情况数。转移方程为：dp[i][j]=dp[i-1][j-a]+dp[i-1][j-b]，其中a、b分别是第i个大集合中两个小集合的大小。如果dp[大集合数][好人总数]==1，说明可以确定。

代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXP = 310;
int n, p, q;
int fa[MAXP*2];
bool same[MAXP*2];
int dp[MAXP*2][MAXP];
int id[MAXP*2], nid;
vector<int> cnt[MAXP*2][2];

void makeFa() {
    for (int i = 1; i <= p+q; i++) {
        fa[i] = i;
        same[i] = true;
    }
}

int find(int x) {
    if (x == fa[x]) return x;
    int fx = find(fa[x]);
    same[x] = same[x] == same[fa[x]];
    fa[x] = fx;
    return fx;
}

bool merge(int x, int y, bool r) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return false;
    same[fy] = same[x] == same[y] == r;
    fa[fy] = fx;
    return true;
}

void makeIdCnt() {
    for (int i = 1; i <= p + q; i++) {
        if (i == fa[i]) {
            id[i] = ++nid;
        }
    }
    for (int i = 1; i <= p + q; i++) {
        int fx = find(i);
        cnt[id[fx]][same[i]].push_back(i);
    }
}

void solve() {
    dp[0][0] = 1;
    for (int i = 1; i <= nid; i++) {
        for (int j = 0; j <= p; j++) {
            if (cnt[i][0].size() <= j)
                dp[i][j] += dp[i - 1][j - cnt[i][0].size()];
            if (cnt[i][1].size() <= j)
                dp[i][j] += dp[i - 1][j - cnt[i][1].size()];
        }
    }
    if (dp[nid][p] == 1) {
        vector<int> ans;
        int sum = p;
        for (int i = nid; i >= 1; i--) {
            if (dp[i - 1][sum - cnt[i][0].size()] == 1) {
                ans.insert(ans.end(), cnt[i][0].begin(), cnt[i][0].end());
                sum -= cnt[i][0].size();
            }
            else {
                ans.insert(ans.end(), cnt[i][1].begin(), cnt[i][1].end());
                sum -= cnt[i][1].size();
            }
        }
        sort(ans.begin(), ans.end());
        for (int it : ans) {
            printf("%d\n", it);
        }
        puts("end");
    }
    else {
        puts("no");
    }
}

void init() {
    makeFa();
    nid = 0;
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= p + q; i++) {
        cnt[i][0].clear();
        cnt[i][1].clear();
    }
}

int main() {
    while (scanf("%d%d%d", &n, &p, &q) == 3 && (n || p || q)) {
        init();
        for (int i = 0; i < n; i++) {
            int a, b;
            char c[4];
            scanf("%d%d%s", &a, &b, c);
            merge(a, b, *c == 'y');
        }
        makeIdCnt();
        solve();
    }
    return 0;
}

H - Arctic Network

题意

题目的大概意思是，两个地点如果各有一个satellite channel，那么无论它们相隔多远都能通信，而如果任何一个没有satellite channel的话，就只能靠radio通信，而radio通信的成本与距离D是成正比的，现在希望让所有地点都能直接或者间接通信，问最小的D是多少。

思路

最小生成树有两个特点，一个是保证了所有边的和是最小值，另一个是保证了所有边中的最大值最小。生成树算法每选中一条边就相当于把两个点集合并成了一个点集，最后用n-1条边连成了1个点集。那么我们往回推，n-2条边就连成了2个点集，n-3条边就连成了3个点集……而就这道题而言，我们相当于去求一共有N个点集的最小生成森林，只要取够P-N条边即可。

代码

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>

struct Point
{
    double x;
    double y;
    double dis(const Point& a) const {
        return sqrt((x - a.x)*(x - a.x) + (y - a.y)*(y - a.y));
    }
} point[500];
double lowcost[500];
bool visited[500];
int s, n;
std::multiset<double> rst;

void prim() {
    memset(visited, 0, sizeof visited);
    rst.clear();
    for (int i = 0; i < n; i++) {
        lowcost[i] = 1e308;
    }
    int u = 0;
    for (int i = 0; i < n - 1; i++) {
        visited[u] = true;
        double nextlen = 1e308;
        int nu = -1;
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                lowcost[v] = std::min(lowcost[v], point[u].dis(point[v]));
                if (lowcost[v] < nextlen) {
                    nextlen = lowcost[v];
                    nu = v;
                }
            }
        }
        u = nu;
        rst.insert(nextlen);
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &s, &n);
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &point[i].x, &point[i].y);
        }
        prim();
        std::multiset<double>::iterator it = rst.begin();
        for (int i = 0; i < n - s-1; i++) {
            it++;
        }
        printf("%.2f\n", *it);
    }
    return 0;
}

I - There is No Alternative

题意

给定一个N个点，M条边的简单连通无向图。 对于一个无向图来说，它的最小生成树可能不是唯一的。 问在它的所有的最小生成树中共有的边是哪几条，输出边数和权值之和。 3<=N<=500, N-1<=M<=min{50000, N(N-1)/2}

思路

首先跑一遍Kruskal，得到最小生成树的权值。 之后尝试删去图中的边，如果某一条边被删去后，最小生成树的值发生了变化（一定变大），那么说明这条边是在所有的最小生成树中都不可或缺的，那么就把这条边加入到答案中。 注意到第一次Kruskal得到的边已经包含了所有的答案，因此只要枚举这里的N-1条边即可。 边排序的复杂度被均摊了，并查集的复杂度可以忽略，因此总的复杂度是O(NM)

代码

#include <cstdio>
#include <algorithm>

const int MAXN = 510, MAXM = 50010;
int n,m;
struct Edge {
    int u, v, c;
    bool operator< (const Edge& b) const {
        return c<b.c;
    }
} e[MAXM];
int possEdge[MAXN];
int cnt;
int ans, ans1, ans2;

int fa[MAXN];

int find(int x) {
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx==fy)
        return false;
    fa[fx] = fy;
    return true;
}

void makeFa() {
    for(int i=1; i<=n; i++) {
        fa[i] = i;
    }
}

void firstKrus() {
    ans = 0;
    cnt = 0;
    makeFa();
    for(int i=0; i<m; i++) {
        if(merge(e[i].u, e[i].v)) {
            ans += e[i].c;
            possEdge[cnt++] = i;
            if(cnt==n-1)
                break;
        }
    }
}

bool krusWithout(int ce) {
    makeFa();
    int sum = 0, ct = 0;
    for(int i=0; i<m; i++) {
        if(i==ce) continue;
        if(merge(e[i].u, e[i].v)) {
            ct++;
            sum+=e[i].c;
            if(sum>ans)
                return false;
            if(ct==cnt)
                return true;
        }
    }
    return false;
}

void tryCut() {
    ans1 = ans2 = 0;
    for(int i=0; i<cnt; i++) {
        if(!krusWithout(possEdge[i])) {
            ans1++;
            ans2+=e[possEdge[i]].c;
        }
    }
}

int main() {
    while(scanf("%d%d", &n, &m)==2) {
        for(int i=0; i<m; i++) {
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
        }
        std::sort(e, e+m);
        firstKrus();
        tryCut();
        printf("%d %d\n", ans1, ans2);
    }
    return 0;
}

J - Frogger

题意

求一条路径，从第一个点能到第二个点，并且这个路径上的最大边权是最小的。

思路

郭华阳在国家集训队论文里介绍了最小生成树的性质，就是在kruskal算法执行的时候第一次将两个点（或者说两个点的集合）连起来的那条边就是这两点的最小瓶颈路上最大边（因为kruskal是从小到大依次连边的）。一旦明白了让这条性质这题就变得简单多了。

代码

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 210;
int n;
struct Point {
    int x, y;
} p[MAXN];
struct Edge {
    int u, v;
    double w;
    bool operator< (const Edge& b) const {
        return w < b.w;
    }
} e[MAXN*MAXN];
int coe;
int fa[MAXN];

void makeFa() {
    for (int i = 0; i < n; i++) {
        fa[i] = i;
    }
}

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return false;
    fa[fx] = fy;
    return true;
}

int main() {
    int cs = 0;
    while (scanf("%d", &n) == 1 && n) {
        cs++;
        coe = 0;
        makeFa();
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &p[i].x, &p[i].y);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                e[coe++] = { i,j,hypot(p[i].x - p[j].x, p[i].y - p[j].y) };
            }
        }
        sort(e, e + coe);
        for (int i = 0; i < coe; i++) {
            merge(e[i].u, e[i].v);
            if (find(0) == find(1)) {
                printf("Scenario #%d\nFrog Distance = %.3f\n\n", cs, e[i].w);
                break;
            }
        }
    }
    return 0;
}