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

S+01Z07【入门】道路规划

描述

有N个村庄,编号从1到N,请你建立一些道路,使得任意两个村庄可以相连。我们说两个村A和B是相连的,当且仅当有一条公路在A与B之间,或存在一个村庄C,有一条的道路连接着A和C之间,一条连接着B和C。

我们知道,已经有一些道路在一些村庄之间,你的工作是再建一些道路,使得所有的村庄连接并且所有的道路建造总和最低。

输入描述

第一行是一个整数N(3 <= N <= 100),表示村庄的数量。接下来N行,每行包含N个整数,在这N行中的第i行的第j个整数Aij表示村庄i到村庄j建立道路的费用 (1 <= Aij <= 1000)。

然后有一个整数Q(0 <= Q <= N *(N + 1)/2)。接下来再Q行,每一行包含两个整数a和b(1 <= a < b <= N),即村庄a和b之间已经建成道路。

输出描述

你应该输出一行包含一个整数,表示所有村庄都连接所要建设道路的最小费用。

用例输入 1

3
0 990 692
990 0 179
692 179 0
1
1 2

用例输出 1

179

代码

注意⚠️:这里村庄编号从0开始

#include<bits/stdc++.h>
using namespace std;
int n,m,num[11000],sz[11000],k,ans,jishu;
struct Node{
    int x,y,w;
}a[110000];
////查询根结点 路径压缩
int find(int x){
    if(num[x]==x) return x;
    return num[x] = find(num[x]);
}
void he(int a,int b,int w){
    //查询是否为一个根结点 一个根结点说明是一个集合,合并的话就会产生回路
    int fa = find(a);
    int fb = find(b);
    if(fa!=fb){
        //计算花费 和 修的路
        ans++;
        jishu+=w;
        if(ans==n-1){ //修到n-1条路,输出总花费
            cout<<jishu;
            exit(0);
        }
        //按秩合并 根据树的大小选择父结点
        if(sz[fa]<sz[fb]) swap(fa,fb);
        num[fb] = fa;
        sz[fa]+=sz[fb];
    }
}
//根据Node结构体的花费W进行升序
bool cmp(Node a,Node b){
    return a.w<b.w;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int w;
            cin>>w;
            if(i<j){
                a[k].x = i;
                a[k].y = j;
                a[k].w = w;
                k++;
            }
        }
    }
    //初始化并查集数组
    for(int i=1;i<=n;i++){
        num[i] = i;
        sz[i]=1;
    }
    cin>>m;
    //合并已有道路,花费为0
    for(int i=0;i<m;i++){
        int q,w;
        cin>>q>>w;
        he(q,w,0);
    }
    sort(a,a+k,cmp);
    for(int i=0;i<k;i++){
        he(a[i].x,a[i].y,a[i].w);
    }
    return 0;
}

S+01Z08【入门】重建电路

描述

小A同学所在的城市遭受了洪灾，城市中的电路受到了严重的破坏。政府部门一方面要救灾，一方面要用最小的代价来重建电路系统。

现在已知该城市有若干个村庄（编号为0~n-1），并已知村庄之间如果重建电路所需要的花费，请你编程帮助该城市计算出，如果要使得该城市恢复电路系统，最少的花费是多少？请注意：只需要保证任意两个村庄之间至少存在一条通路，电路系统即可恢复。

输入描述

输入的第一行为一个整数T（1<=T<=50），表示有T组测试数据。

每组输入第一行是两个正整数N，E（2<=N<=500，N<=E<=N*(N-1)/2），分别表示该城市村庄个数和原有电力线路的个数。

接下来的E行，每行包含三个整数A，B，K（0<=A,B<N，0<=K<1000）。A和B分别表示电力线路的起始村庄代号。如果K=0，表示这条线路仍然正常。如果K是一个正整数，表示这条线路需要花费K的代价来重建。
题目保证输入中没有重边，也没有起始村庄相同的边。本题的数据确保一定能重建电路系统。

输出描述

对于每组输入，输出重建电力系统所需的最小花费，以此来保证任意两个村庄之间至少存在一条通路。

用例输入 1

1
3 3
0 1 5
0 2 0
1 2 9

用例输出 1

5

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,m,num[11000],sz[11000],ans,jishu;
struct Node{
    int x,y,w;
}a[910000];
////查询根结点 路径压缩
int find(int x){
    if(num[x]==x) return x;
    return num[x] = find(num[x]);
}
void he(int a,int b,int w){
    //查询是否为一个根结点 一个根结点说明是一个集合,合并的话就会产生回路
    int fa = find(a);
    int fb = find(b);
    if(fa!=fb){
        //计算花费 和 修的路
        ans++;
        jishu+=w;
        //按秩合并 根据树的大小选择父结点
        if(sz[fa]<sz[fb]) swap(fa,fb);
        num[fb] = fa;
        sz[fa]+=sz[fb];
    }
}
//根据Node结构体的花费W进行升序
bool cmp(Node x,Node y){
    return x.w<y.w;
}
int main(){
    cin>>t;
    for(int j=0;j<t;j++){
        cin>>n>>m;
        for(int i=0;i<m;i++){
            cin>>a[i].x>>a[i].y>>a[i].w;
        }
        sort(a,a+m,cmp);
        for(int i=0;i<n;i++){
            num[i] = i;
            sz[i] = 1;
        }
        for(int i=0;i<m;i++){
            he(a[i].x,a[i].y,a[i].w);
            if(ans==n-1){ //修到n-1条路,输出总花费
                cout<<jishu<<endl;
                break;
            }
        }
        ans = 0,jishu = 0;
    }
    return 0;
}

S+01Z09【入门】片区划分

描述

A市有n个村庄（村庄编号为1~n），现准备将n个村庄划分为k个区（一个区中要有至少1个村庄），同一个区中的村庄要求有道路可以互相到达（不一定要直达，比如：A村要去C村，可以先先去B村，再去C村）。

为了节约成本，在划分之前，相关规划部门调研了村庄之间修路的成本，本次调研，共调研到了m条道路的建设成本。

假设所有村庄之间目前没有任何道路，如果要将n个村庄划分为k个区，请求出最少的修路成本？

输入描述

第一行有三个数n,m,k(1≤n≤1000,1≤m≤10000,1≤k≤10)

接下来m行每行三个数x,y,l，表示编号为x村到编号为y村修路的费用。(1≤x,y≤n,0≤l<10000)

测试数据保证x村到y村的道路只有1条。

输出描述

输出一个整数，代表最少的修路成本。

如果按照当前的调研数据，无法将n个村庄划分为k个区，请输出"No Answer"（比如，假设有5个村庄，只有2条道路的建设数据，是无法将5个村庄划分为2个区或者1个区的）。

用例输入 1

3 1 2
1 2 1

用例输出 1

1

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,num[1100],k,cns,jishu;
struct Node{
    int x,y,v;
}a[11000];
bool cmp(Node a,Node b){
    return a.v<b.v;
}
int find(int x){
    return num[x]==x? x : num[x] = find(num[x]);
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int x,y,v;
        cin>>x>>y>>v;
        a[i].x = x;
        a[i].y = y;
        a[i].v = v;
    }
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=n;i++) num[i]=i;
    for(int i=1;i<=m;i++){
        int fa = find(a[i].x);
        int fb = find(a[i].y);
        if(fa!=fb){
            cns++;
            jishu+=a[i].v;
            if(cns==n-k){
                cout<<jishu;
                return 0;
            }
            num[fb] = fa;
        }
    }
    cout<<"No Answer";
    return 0;
}

作业: S+01Z04

S+01Z04【基础】采购礼品 背包并查集

描述

王老师来到商店为同学们采购礼品。这家店有n种礼品（编号是1~n），每种礼品只有1件。老板为了促销，对礼品进行搭配销售，有关联性的礼品必须都要采购（奇怪的规定），比如1号礼品和3号礼品搭配了，3号和8号礼品搭配了，那么王老师想要买1号礼品的话，就需要把3号和8号礼品都买了。现给定每种礼品的价钱和价值，请问在有限的钱w的情况下，能够买到礼品的最大价值是多少？

输入描述

第一行输入三个整数，n,m,w，表示有n种礼品，m个搭配和你现有的钱的数目。

第二行至n+1行，每行有两个整数，c、d，表示第i种礼品的价钱和价值。（1≤c,d≤105）

第n+2至n+1+m行 ，每行有两个整数，u、v，表示u号礼品和v号礼品是有关联的，已经形成搭配销售的关系。

1≤n,w≤104,0≤m≤5×103。

输出描述

一行，表示可以获得的最大价值。

用例输入 1

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

用例输出 1

1

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,w;//n种礼品，m个搭配 w钱
int num[11000],dp[11000];
struct Node{
    int p,v;//p价格  v价值
}a[11000];//a数组存以i为根结点的集合总价格和总价值
int find(int x){
    return num[x]==x ? x : num[x] = find(num[x]);
}
int main(){
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++){
        cin>>a[i].p>>a[i].v;
    }
    //开始并查集
    for(int i=1;i<=n;i++){
        num[i] = i;
    }
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        int fa = find(x);
        int fb = find(y);
        if(fa!=fb) {
            num[fb] = fa;
            a[fa].p += a[fb].p;
            a[fa].v += a[fb].v;
        }
    }
    //01背包
    for(int i=1;i<=n;i++){
        if(num[i]==i){
            for(int j=w;j>=a[i].p;j--){
                dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v);
            }
        }
    }
    cout<<dp[w];
    return 0;
}