11月1日星期六18:30-21:00

S+01Z01【基础】舞伴

描述

小明在A公司工作，小红在B公司工作。这两个公司的员工有一个特点：一个公司的员工都是同性。A公司有N名员工，其中有P对朋友关系。B公司有M名员工，其中有Q对朋友关系。

朋友的朋友一定还是朋友。每对朋友关系用两个整数(Xi,Yi)组成，表示朋友的编号分别为Xi，Yi。男人的编号是正数，女人的编号是负数。小明的编号是1，小红的编号是-1。

大家都知道，小明和小红是朋友。现举办一场舞会，每个人要找一个异性作为自己的舞伴，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能组成多少对舞伴。（包括他们自己）

输入描述

第1行，4个空格隔开的正整数N,M,P,Q。

之后P行，每行两个正整数Xi，Yi。

之后Q行，每行两个负整数Xi，Yi。

N,M<=10000,P,Q<=20000。

输出描述

一行，一个正整数，表示通过小明和小红认识的人最多一共能组成多少对舞伴。（包括他们自己）

用例输入 1

1 1
1 2
2 3
1 3
-1 -2
-3 -3

用例输出 1

2

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,num[21000],a,b,mi=INT_MAX;
//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() {
    int n,m,p,q;
    cin>>n>>m>>p>>q;
    //初始化num数组
    for(int i=1;i<=n;i++){
        num[i]=i;
        sz[i]=1;
    }
    for(int i=0;i<p;i++){
        cin>>a>>b;
        he(a,b);
    }
    a = find(num[1]);
    //把小明这个集合的结点数给 mi
    mi = min(sz[a],mi);//mi = sz[a] 一个意思
    //初始化num数组
    for(int i=1;i<=m;i++){
        num[i]=i;
        sz[i]=1;
    }
    for(int i=0;i<q;i++){
        cin>>a>>b;
        he(abs(a),abs(b));
    }
    a = find(num[1]);
   //和小红这个集合的结点数比较 取最小值
    mi = min(sz[a],mi);
    cout<<mi;
    return 0;
}

S+01L03 躲避拥堵的最佳路线

描述

小明所在的城镇有m条路连接了n个区（n个区的编号在1~n的范围内），每条大道将两个区相连接，每条大道有一个拥挤度。小明想要开车从s区去t区，请你帮他规划一条路线，使得经过道路的拥挤度的最大值最小。

输入描述

第一行有四个用空格隔开的n，m，s，t，其含义见题目描述。

接下来m行，每行三个整数u,v,w，表示有一条大道连接区u和区v，且拥挤度为w。

两个区之间可能存在多条大道。

数据规模与约定
对于 30% 的数据，保证n≤10。
对于 60% 的数据，保证n≤100。
对于 100% 的数据，保证1≤n≤10^4，1≤m≤2×10^4, w≤10^4,1≤s,t≤n。且从 s 出发一定能到达 t 区。

输出描述

输出一行一个整数，代表最大的拥挤度。

用例输入 1

3 3 1 3
1 2 2
2 3 1
1 3 3

用例输出 1

2

代码

#include<bits/stdc++.h>
using namespace std;
int num[11000],sz[11000];
// 区 关系 起点 终点
int n,m,s,t;
int l=INT_MAX,r=INT_MIN,mid;
struct Node{
    int u;
    int v;
    int w;//拥挤度
}a[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];
    }
}
//判断该拥挤度是否符合要求 
//把小于等于该拥挤度的路修起来(合并),能从起点走到终点,说明这个拥挤度可能过大或者刚刚好,为了求最小值继续往左边查找
//如果不能从起点走到终点,说明这个拥挤度过小,继续往右边边查找
bool check(int mid){
    for(int i=1;i<=n;i++){
        num[i]=i;
        sz[i]=1;
    }
    for(int i=0;i<m;i++){
        if(a[i].w<=mid){
            he(a[i].u,a[i].v);
        }
    }
    return find(s)==find(t);
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
        l = min(l,a[i].w);
        r = max(r,a[i].w);
    }
    while(l<=r){
        mid = l+r>>1;
        if(check(mid)){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout<<l;
    return 0;
}

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

6
4
E 1 4
F 3 5
F 4 6
E 1 2

用例输出 1

3

提示

样例结束：[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 关押罪犯