最小生成树的典型应用
AcWing 1140. 最短网络
题目
https://www.acwing.com/problem/content/1142/
农夫约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。
约翰的农场的编号是1，其他农场的编号是 2∼n。
为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。
你将得到一份各农场之间连接距离的列表，你必须找出能连接所有农场并使所用光纤最短的方案。
思路
最小生成树板子题，直接背模板。
代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=110;
int n;
int g[N][N];
int dist[N];
bool st[N];
int prim()
{
int res=0;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
}
res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],g[t][j]);
}
}
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>g[i][j];
cout<<prim();
return 0;
}
AcWing 1141. 局域网
题目
https://www.acwing.com/problem/content/1143/
某个局域网内有 n 台计算机和 k 条 双向 网线，计算机的编号是 1∼n。由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。
注意：
对于某一个连接，虽然它是双向的，但我们不将其当做回路。本题中所描述的回路至少要包含两条不同的连接。 两台计算机之间最多只会存在一条连接。 不存在一条连接，它所连接的两端是同一台计算机。 因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用 f(i,j) 表示 i,j 之间连接的畅通程度，f(i,j) 值越小表示 i,j 之间连接越通畅。
现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路且不影响连通性（即如果之前某两个点是连通的，去完之后也必须是连通的），并且被除去网线的 Σf(i,j) 最大，请求出这个最大值。
思路
题目要求删掉其中的部分边，在不改变图的连通性的情况下，使图中无环且所删边和最大，输出最大的所删边边权权和。 要求删除边权和最大，只要求剩下边权和最小，只要求最小生成 树， 本题图不一定连通，只要对每个连通块，求最小生成树。
代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=110,M=210;
int n,m;
int p[N];
struct edge
{
int a,b,w;
bool operator<(const edge &W) const
{
return w<W.w;
}
}edges[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;//初始化并查集
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edges[i]={a,b,w};
}
sort(edges,edges+m);
int res=0;
for(int i=0;i<m;i++)
{
int a=find(edges[i].a),b=find(edges[i].b);
if(a!=b) p[a]=b;
else res+=edges[i].w;
}
cout<<res<<endl;
return 0;
}
AcWing 1142. 繁忙的都市
题目
https://www.acwing.com/problem/content/1144/
城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。
城市C的道路是这样分布的：
城市中有 n 个交叉路口，编号是 1∼n，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。
这些道路是 双向 的，且把所有的交叉路口直接或间接的连接起来了。
每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。
但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大值尽量小。
作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建。
思路
做法：kruskal
1、将所有边从小到大排序
2、枚举每条边a,b,权值是w，如果 a和b不连通，将a，b加进集合，且更新res
Kruskal 能够很好的应用此题，由于 它的贪心性质，从小到大枚举所有边，所以一旦枚举完 m 条边，最后加进去的那条边一定就是我们要求的边。
由此可见，由 Kruskal 算法求出的最小生成树，不但总权值和最小，而且最大边的边权一定是所有的生成树最大边中最小的。
代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=310,M=10010;
int n,m;
int p[N];
struct edge
{
int a,b,w;
bool operator <(const edge &W) const
{
return w<W.w;
}
}edges[M];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edges[i]={a,b,w};
}
sort(edges,edges+m);
int res=0;
for(int i=0;i<m;i++)
{
int a=find(edges[i].a),b=find(edges[i].b),w=edges[i].w;
if(a!=b)
{
p[a]=b;
res=w;
}
}
cout<<n-1<<" "<<res<<endl;
return 0;
}
AcWing 1143. 联络员
题目
https://www.acwing.com/problem/content/1145/ Tyvj已经一岁了，网站也由最初的几个用户增 加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。本题中所涉及的通信渠道都是 双向 的。 Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。 目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。 数据保证给出的通信渠道可以让所有的管理员联通。 注意： 对于某两个管理员 u,v，他们之间可能存在多条通信渠道，你的程序应该累加所有 u,v 之间的必选通行渠道。
思路
分为必选边和非必选边
- 将所有必选边加到并查集中
- 将所有非必选边从小到大排序
- 从小到大依次枚举每一条非必选边，a,b,w,
- 如果a,b已经连通，直接pass
- 如果a，b不连通，那么就将当前边选上
代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=2010,M=10010;
int n,m;
int p[N];
struct edge
{
int a,b,w;
bool operator <(const edge &W) const
{
return w<W.w;
}
}edges[M];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
int res=0,k=0;
for(int i=0;i<m;i++)
{
int t,a,b,w;
cin>>t>>a>>b>>w;
if(t==1)
{
res+=w;
p[find(a)]=find(b);
}
else edges[k++]={a,b,w};
}
sort(edges,edges+k);
for(int i=0;i<k;i++)
{
int a=find(edges[i].a),b=find(edges[i].b),w=edges[i].w;
if(a!=b)
{
p[a]=b;
res+=w;
}
}
cout<<res;
return 0;
}
AcWing 1144. 连接格点
题目
https://www.acwing.com/problem/content/1146/ 有一个 m 行 n 列的点阵，相邻两点可以相连。 一条纵向的连线花费一个单位，一条横向的连线花费两个单位。 某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。
思路
做一遍kruskal，原有边这个东西只需要把并查集连上就可以，不需要排序 因为竖边费用一定比横边小，只需要枚举所有竖边，再枚举第一行的所有横边（竖边加完后横边加在 第几行都一样）
代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1010,M=N*N,K=2*N*N;
int n,m;
int ids[N][N];
int k;
struct edge
{
int a,b,w;
}e[K];
int p[M];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void get_edges()
{
int dx[]={-1,0,1,0},dy[]={0,1,0,-1},dw[]={1,2,1,2};
for(int z=0;z<2;z++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int u=0;u<4;u++)
{
if(u%2==z)//u是0和2
{
int x=i+dx[u],y=j+dy[u],w=dw[u];
if(x&&x<=n&&y&&y<=m)
{
int a=ids[i][j],b=ids[x][y];
if(a<b) e[k++]={a,b,w};
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1,t=1;i<=n;i++)
for(int j=1;j<=m;j++,t++)
ids[i][j]=t;
for(int i=1;i<=n*m;i++) p[i]=i;
int x1,y1,x2,y2;
while(cin>>x1>>y1>>x2>>y2)
{
int a=ids[x1][y1],b=ids[x2][y2];
p[find(a)]=find(b);
}
get_edges();
int res=0;
for(int i=0;i<k;i++)
{
int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
if(a!=b)
{
p[a]=b;
res+=w;
}
}
cout<<res<<endl;
return 0;
}