MENU

0712并查集题解

July 14, 2020 • Read: 62 • 题解

P2024食物链

关键词:并查集 种类并查集

题目描述

动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。A 吃 B,B 吃 C,C 吃 A。

现有 N 个动物,以 1 - N 编号。每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述:

  • 第一种说法是 1 X Y,表示 X 和 Y 是同类。
  • 第二种说法是2 X Y,表示 X 吃 Y 。

此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

  • 当前的话与前面的某些真的话冲突,就是假话
  • 当前的话中 X 或 Y 比 N 大,就是假话
  • 当前的话表示 X 吃 X,就是假话

你的任务是根据给定的 N 和 K 句话,输出假话的总数。

输入格式

第一行两个整数,N,K,表示有 N 个动物,K 句话。

第二行开始每行一句话(按照题目要求,见样例)

输出格式

一行,一个整数,表示假话的总数。

输入输出样例

输入 #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

输出 #1

3

说明/提示

1 ≤ N ≤ 5 ∗ 10^4
1 ≤ K ≤ 10^5

题解

思路:利用三倍的并查集存储各种动物的关系,一倍存同类,二倍存猎物,三倍存天敌

记住,敌人的敌人就是朋友,朋友的朋友还是朋友,剩下的就是代码了

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-07-14 15:22:30
 * @Website: https://grimoire.cn
 * @Mr.Sen All rights reserved
 */ 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+10;
const int NN = 300005;
int ranks[NN];
int parent[NN];


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

void toUnion(int x1, int x2) {
    int p1 = find(x1);
    int p2 = find(x2);

    if (ranks[p1] > ranks[p2]) {
        parent[p1] = p2;
    } else {
        parent[p2] = p1;
        
        if (ranks[p1] == ranks[p2]) {
            ranks[p2]++;
        }
    }
}

void init(int n)
{
    for (int i = 1; i <= 3*n; i++)
    {
        parent[i] = i;
    }
}


int main()
{
    int N,K;
    cin>>N>>K;
    init(N);
    int ans = 0;
    for (int i = 1; i <= K; i++)
    {
        int type,x,y;
        scanf("%d%d%d",&type,&x,&y);
        if (x > N || y > N)
        {
            ans++;
            continue;
        }
        if (type == 1)    // 同类关系
        {
            if (find(x + N) == find(y) || find(x + 2*N) == find(y))
            {
                ans++;
                continue;
                // 同类关系与猎物、天敌关系相矛盾
            }
            else // 说真话
            {
                toUnion(x,y);    // x和y是同类
                toUnion(x + N,y + N);    // x的猎物就是y的猎物
                toUnion(x + 2 * N,y + 2 * N);    // x的天敌就是y的天敌
            }
            
        }
        if (type == 2)    // 捕食关系: x => y
        {
            if (find(x) == find(y) || find(x + 2 * N) == find(y))
            {
                ans ++;
                continue;
                // 捕食关系不包括同类,另外捕食者不能成为被捕食者
            }
            else // 说真话
            {
                toUnion(x , y + 2 * N); // x 的同类是 y 的天敌
                toUnion(x + N ,y);    // x 的猎物 y 的同类
                toUnion(x + 2 * N, y + N); // x 的天敌是 y 的猎物
                
            }
        }
    }

    cout<<ans<<endl;
    return 0;
}

P3366最小生成树(模板题)

关键字:克鲁斯卡尔算法 、生成树、并查集

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz

输入格式

第一行包含两个整数 N,MN,M,表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 X_i,Y_i,Z_i表示有一条长度为 Z_i的无向边连接结点 X_i,Y_i

输出格式

如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz

输入输出样例

输入

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出

7

说明/提示

数据规模:

对于 20% 的数据,N≤5,M≤20。

对于 40% 的数据,N≤50,M≤2500。

对于 70% 的数据,N≤500,M≤104。

对于 100% 的数据:1≤N≤5000,1≤M≤2×105。

样例解释:

img

所以最小生成树的总边权为2+2+3=7

题解

模板题,照着模板背就行了,切记别背错模板啊

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-07-14 20:36:05
 * @Website: https://grimoire.cn
 * @Mr.Sen All rights reserved
 */ 

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int u,v,w;
}lst[200005];

int parent[200005];
int ranks[200005];

bool cmp(node s1, node s2) {
    return s1.w < s2.w;
}

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

void toUnion(int x1, int x2) {
    int p1 = find(x1);
    int p2 = find(x2);

    if (ranks[p1] > ranks[p2]) {
        parent[p1] = p2;
    } else {
        parent[p2] = p1;
        
        if (ranks[p1] == ranks[p2]) {
            ranks[p2]++;
        }
    }
}

int main() {
    int n,m,sum1 = 0;
    cin>>n>>m;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &lst[i].u, &lst[i].v, &lst[i].w);
        sum1 += lst[i].w;
    }
    sort(lst + 1,lst + m + 1,cmp);

    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
    }

    int sum = 0, tot = 0, flag =0;

    for (int i = 1; i <= m; i++)
    {
        int u = lst[i].u;
        int v = lst[i].v;
        int w = lst[i].w;

        if (find(u) != find(v)) {
            toUnion(u, v);
            sum += w;
            tot++;
        }

        if (tot == n - 1 ) {
            flag = 1;
            break;
        }
        // 这里老师的模板有误,有的数据会被卡,所以我给改了
    }
    if (flag == 1) {
        cout<<sum<<endl;
    } else {
        cout<<"orz"<<endl;
    }
    
    return 0;
}

林大OJ 藤原千花的星星图

Description

藤原千花很喜欢星星,她有一个很大的星星图,图中一共有n个星星(序号为1-n),但是千花看到这些星星散乱分布很不开心,她想将这些星星连起来,让任意两个星星都直接或者间接相连。但是并不是任意两个星星都可以直接相连的,一共有m组星星可以相连。题目将给出这m组可相连星星的信息,每组包含三个整数,分别是两个星星的序号和将这两个星星连起来需要付出的代价。问千花可否让所有星星都直接或间接的连接起来?如果不可以的话请输出“-1”,如果可以,请输出需要付出最小总代价。

Input

多组输入
每组第一行一个整数n(2<=n<=1e6)
第二行一个整数m(m<=1e6)
接下来m行
每行三个数,分别为可连接的两个星星的序号ai,aj和连接这两个星星的代价整数w(1<=ai<=n,1<=aj<=n, ai!=aj , 1<=w<=1e8 )

Output

每组输出一个整数,如果不能使所有星星都连接起来输出“-1”(没有引号)
否则输出需要付出最小总代价。

Sample Input

4 
3
1 3 15
2 3 4
1 2 49

4 
5
1 2 1
1 3 2
2 3 3
2 4 4
3 4 5

Sample Output

-1
7

Hint

第一组样例,不论如何都不能将4个星星连在一起,所以输出-1
第二组样例,我们将第一组,第二组和第四组中的两个星星分别连起来可以以最小总代价达到题目要求,总代价是7

题解

这题...一言难尽啊,因为老师给的模板本身存在问题,一直卡数据,所以这题我提交了13次都没有过

后来发现这个问题了之后就一发就A了

/*
 * @Author: Mr.Sen
 * @LastEditTime : 2020-07-13 23:38:29
 * @Website: https://grimoire.cn
 * @Mr.Sen All rights reserved
 */
#pragma GCC optimize(2)
// 本题正解不是使用的克鲁斯卡尔算法,而是prim算法
// 使用前者会被卡时间,因此这里加入了o2优化强过
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;
struct node
{
    int u, v;
    long long w;
} lst[MAXN];

int parent[MAXN];

bool cmp(node s1, node s2)
{
    return s1.w < s2.w;
}

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

void toUnion(int x1, int x2)
{
    int p1 = find(x1);
    int p2 = find(x2);
    
    parent[p2] = p1;
}

int main()
{
    int n, m, sum1 = 0;
    while (cin >> n >> m)
    {
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%lld", &lst[i].u, &lst[i].v, &lst[i].w);
        }
        sort(lst + 1, lst + m + 1, cmp);

        for (int i = 1; i <= n; i++)
        {
            parent[i] = i;
        }

        long long sum = 0;
        int tot = n, flag = 0;

        for (int i = 1; i <= m; i++)
        {
            
            int u = lst[i].u;
            int v = lst[i].v;
            long long w = lst[i].w;

            if (find(u) != find(v))
            {
                toUnion(u, v);
                // sum += w;
                sum += w;
                tot--;
            }
            if (tot == 1)
            {
                // cout<<"dio"<<endl;
                flag = 1;
                break;
            }
        }
        
        if (flag != 1)
        {
            cout<<-1<<endl;
        }
        else
        {
            cout<<sum<<endl;
        }   
    }
    return 0;
}

林大OJ 一道图论一

Description

给定一个包含 n 个节点和 m 条边的图,每条边有一个权值。
你的任务是回答 k 个询问,每个询问包含两个正整数 s 和 t 表示起点和终点,要求寻找从 s 到 t 的一条路径,使得路径上权值最大的一条边权值最小。

Input

第一行包含三个整数 n 、m 、k ,分别表示 n 个节点, m 条路径, k 个询问。

接下来 m 行,每行三个整数 u , v , w, 表示一个由 u 到 v 的长度为 w 的双向边。

再接下来 k 行,每行两个整数 s , t,表示询问从 s 连接到 t 的所有路径中单边长度最大值的最小值。

Output

输出包含 k 行,每一行包含一个整数 p 。p 表示 s 连接到 t 的所有路径中单边长度最大值的最小值。另外,如果 s 到 t 没有路径相连通,输出 -1 即可。

Sample Input

8 11 3
1 2 10
2 5 50
3 4 60
7 5 60
3 6 30
1 5 30
6 7 20
1 7 70
2 3 20
3 5 40
2 6 90
1 7
2 8
6 2

Sample Output

30
-1
30

Hint

对于 100% 的数据 n≤1000,m≤100000,k≤1000,w≤10000000
本题可能会有重边。
为了避免 Special Judge,本题所有的 w 均不相同。

题解

我直接放代码吧

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-07-14 20:15:15
 * @Website: https://grimoire.cn
 * @Mr.Sen All rights reserved
 */

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int parent[N];

struct node
{
    int u, v, w;
} vis[N], ask[N];

bool cmp(struct node x, struct node y)
{
    return x.w < y.w;
}

int find(int x)
{
    int r = x;
    while (r != parent[r])
        r = parent[r];
    int tmp, i = x;
    while (i != r)
    {
        tmp = parent[i];
        parent[i] = r;
        i = tmp;
    }
    return r;
}

void unionSet(int x, int y)
{
    int tmp1 = find(x);
    int tmp2 = find(y);
    if (tmp1 != tmp2)
        parent[tmp1] = tmp2;
}

int main()
{
    int n, m, k;

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
    }
    
    for (int i = 1; i <= m; i++)
    {
        cin >> vis[i].u >> vis[i].v >> vis[i].w;
    }
    sort(vis + 1, vis + 1 + m, cmp);
    // 给所有的路径按照权值来排序

    for (int i = 1; i <= k; i++)
    {
        cin >> ask[i].u >> ask[i].v;
        ask[i].w = -1;
    }
    
    int maxn = 0;
    for (int i = 1; i <= m; i++)
    {
        unionSet(vis[i].u, vis[i].v);
        // 与克鲁斯卡尔算法不同,这里不需要整体权值最小,一个一个来就行
        maxn = vis[i].w;

        for (int j = 1; j <= k; j++)
        {
            if (ask[j].w == -1 && find(ask[j].u) == find(ask[j].v))
            {
                ask[j].w = maxn;
                // 如果这个值暂未被赋值并且两个点连通,则最小的权值就是 maxn 
            }
        }
    }
    for (int i = 1; i <= k; i++)
    {
        cout << ask[i].w << endl;
    }

    return 0;
}

注:截止2020年7月14日,本文代码在林大OJ以及洛谷正常编译通过,但不保证后续依然能通过,特此说明

Archives Tip
QR Code for this page
Tipping QR Code