11月1日星期六9:00-12:00

S+01L04【基础】团队数量

描述

芝加哥组织了一场激烈的军事竞赛，很多国家的军人慕名而来，他们要么是队友，要么是敌人。

现建立如下规则：

我的队友的队友，是我的队友；

我的敌人的敌人也是我的队友；

两个人只要是队友，就认为他们属于同一团队，现给你若干参赛军人之间的关系，请问：最多有多少个团队？

输入描述

第一行是一个整数N(2<=N<=1000)，表示参赛的人数（从1编号到N）。第二行M(1<=M<=5000)，表示关于参赛者的关系信息的条数。以下M行，每行可能是F p q或是E p q（1<=p q<=N），F表示p和q是队友，E表示p和q是敌人。输入数据保证不会产生信息的矛盾。

输出描述

输出文件只有一行，表示最大可能的团队数。

用例输入 1

用例输出 1

提示

样例结束：[3,5]是一个团队，[4,6]是一个团队，由于1和4、1和2都是敌人，2和4自然成为队友，因此[2,4,6]成为团队，1单独为1个团队，最终有3个团队。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,num[21000],p,q,jishu;
string s;
//rank存该根节点所在树的高度 size该根节点所在树的大小
int ra[21000],sz[21000];
//路径压缩写法
int find(int x) {
    if (num[x] == x) return x;
    num[x] = find(num[x]);  // 路径压缩：让 x 直接挂到根节点下
    return num[x];
}
//合并
//按秩合并 树的大小
void he(int f, int z) {
    int fa = find(f);
    int fb = find(z);
    if (fa != fb) {
        // 按树大小合并，小树挂大树
        if(sz[fa]<sz[fb]) swap(fa,fb);
        num[fb] = fa;
        sz[fa] += sz[fb];
    }
}
int main() {
    cin>>n>>m;
    for(int i=1;i<n*2;i++){
        num[i] = i;
    }
    for(int i=0;i<m;i++){
        cin>>s>>p>>q;
        if(s=="F") he(q,p);
        else{
            he(q,p+n);
            he(p,q+n);
        }
    }
    for(int i=1;i<=n;i++){
        if(num[i]==i){
            jishu++;
        }
    }
    cout<<jishu;
    return 0;
}

S+01L05 关押罪犯

描述

S城现有两座监狱，一共关押着N名罪犯，编号分别为1−N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入描述

输入数据的每行中两个数之间用一个空格隔开。

第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨气值为cj。

数据保证1<=aj<=bj<=N,0<=cj<=109,且每对罪犯组合只出现一次。

【数据范围】
对于30%的数据有N≤15。
对于70%的数据有N≤2000，M≤50000。
对于100%的数据有N≤20000，M≤100000。

输出描述

输出数据共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。

用例输入 1

用例输出 1

提示

【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。

代码

#include<bits/stdc++.h>
using namespace std;
int num[110000],sz[110000];
// 区 关系 起点 终点
int n,m;
struct Node{
    int x;
    int y;
    int w;//怨气值
}a[110000];
//路径压缩写法
int find(int x) {
    if (num[x] == x) return x;
    return num[x] = find(num[x]);  // 路径压缩：让 x 直接挂到根节点下
}
//按秩合并 树的大小
void he(int f, int z) {
    int fa = find(f);
    int fb = find(z);
    if (fa != fb) {
        // 按树大小合并，小树挂大树
        if(sz[fa]<sz[fb]) swap(fa,fb);
        num[fb] = fa;
        sz[fa] += sz[fb];
    }
}
bool cmp(Node x,Node y){
    return x.w>y.w;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].x>>a[i].y>>a[i].w;
    }
    //做并查集之前记得初始化 数组和树大小初始化
    for(int i=1;i<=n*2;i++){
        num[i]=i;
        sz[i]=1;//memset(a, 1, sizeof(a)); // ❌错误！
    }
    sort(a,a+m,cmp);
    for(int i=0;i<m;i++){
        if(find(a[i].x)== find(a[i].y)){
            cout<<a[i].w;
            return 0;
        }else{
            he(a[i].x+n,a[i].y);
            he(a[i].y+n,a[i].x);
        }
    }
    cout<<0;
    return 0;
}