11月8日星期六18:30-21:00
S+01L06【基础】最短网络 Agri-Net（USACO3.1）
描述
Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。
FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。
你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 10^5。
输入描述
第一行农场的个数N（3≤N≤100）。
接下来是一个N×N 的矩阵，表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，由于每行80个字符的限制，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。
输出描述
只有一个输出，其中包含连接到每个农场的光纤的最小长度。
用例输入 1
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
用例输出 1
28
代码
#include<bits/stdc++.h>
using namespace std;
//把各个农村之间的距离进行排序
//优先选择距离短的进行合并,并且保证没有回路(判断是否在同一个集合)
//选择n-1段累加起来就是最小花费
int n,t,k,num[110],sz[110],jishu,cns;
struct Node{
int x,y,len;
}a[5000];
//查询根结点
int find(int x){
if(num[x]==x) return x;
return num[x] = find(num[x]);
}
//合并 计算
int he(Node node){
//查询是否为一个根结点 一个根结点说明是一个集合,合并的话就会产生回路
int fa = find(node.x);
int fb = find(node.y);
if(fa!=fb){
cns++;
//把距离累加起来
jishu+=node.len;
//修到n-1段就是所有农场都通网的最小距离
if(cns==n-1){
cout<<jishu;
exit(0);
}
//按照树的大小进行合并
if(sz[fb]>sz[fa]) swap(fa,fb);
num[fb] = fa;
sz[fa]+=sz[fb];
}
}
//根据Node结构体的长度len进行升序
bool cmp(Node a,Node b){
return a.len<b.len;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>t;
if(i<j){
a[k].x = i;
a[k].y = j;
a[k].len = t;
k++;
}
}
}
//排序 初始化数组
sort(a,a+k,cmp);
for(int i=1;i<=n;i++){
num[i] = i;
sz[i] = 1;
}
for(int i=0;i<k;i++){
//cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].len<<endl;
he(a[i]);
}
return 0;
}
S+01Z06【基础】最短的通路时间
描述
某市新规划了N个村庄（村庄编号为1~N），现准备在这N个村庄之间修建M条道路，每条公路的连着两个村庄。已知这M条道路每条路连接了哪两个村庄，以及什么时候这条路能修好。请问：最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修完的道路（两个村庄之间可能有多条路）。
输入描述
第1行两个正整数N,M
下面M行，每行3个正整数x,y,t，告诉你这条公路连着x,y两个村庄，在时间t时能修完成这条公路。
N≤1000,M≤100000
x≤N,y≤N,t≤100000
输出描述
如果全部公路修完仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。
用例输入 1
4 4
1 2 6
1 3 4
1 4 5
4 2 3
用例输出 1
5
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,num[1100],cns;
//按照修路的完成时间进行排序
//先把时间早的路都修好,并且不能有回路,这样当我们修到第n-1条路的时候,这条路的时间就是我们最晚通车的时间
//如果没有修到n-1条路,说明一定有两个村庄没有路,输出-1
//思考: 为什么不能有回路,如果有回路说明什么情况
struct Node{
int x,y,t;
}a[110000];
//查询根结点 路劲压缩
int find(int x){
if(num[x]==x) return x;
return num[x] = find(num[x]);
}
//根据Node结构体的时间t进行升序
bool cmp(Node a,Node b){
return a.t<b.t;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i].x>>a[i].y>>a[i].t;
}
//根据时间t进行升序
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);
//不是一个集合就把路修起来,直到修到n-1条路,输出他的完成时间
if(fa!=fb){
num[fb] = fa;
cns++;
}
if(cns==n-1){
cout<<a[i].t;
return 0;
}
}
cout<<-1;
return 0;
}
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;
}