图的最小生成树应用——洛谷题单
程序员文章站
2022-07-08 10:12:17
P3366 【模板】最小生成树#include#include#include using namespace std;#define maxsize 5005#define maxcost 21000000struct node{int v;//目的地int w;//权值};int n, m;vector < node> g[maxsize];long long in...
P3366 【模板】最小生成树
给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz
一道模板题，prim算法或者kruskal都可以，我们可以给不存在的边设定一个极大值，最后的最小生成树权值和大于极大值则不连通
#include<iostream>
#include<algorithm>
#include <cstring>
using namespace std;
#define maxsize 5005
#define maxcost 21000000
struct node
{
int v;//目的地
int w;//权值
};
int n, m;
vector < node> g[maxsize];
long long int lowcost[maxsize];//保存相关顶点权值
int dis[maxsize];
int prim( int x)
{
int min, min_id;
int sum = 0;
memset(lowcost, maxcost, sizeof(lowcost));
memset(dis, 0, sizeof(dis));
for ( int i=0; i<g[x].size(); i++)
{//务必要选出最小值
if(lowcost[g[x][i].v]> g[x][i].w)
lowcost[g[x][i].v] = g[x][i].w;
}
lowcost[x] = 0;
for (int i=1;i<n;i++)
{
min = maxcost;
min_id = 0;
for (int j = 1; j <= n; j++)
{
if (lowcost[j] <min &&lowcost[j] !=0)
{
min = lowcost[j];
min_id = j;
}
}
sum += min;
lowcost[min_id] = 0;
for (int i = 0; i < g[min_id].size();i++)
{
if (lowcost[g[min_id][i].v] >g[min_id][i].w && lowcost[g[min_id][i].v]!=0)
lowcost[g[min_id][i].v] = g[min_id][i].w;
}
}
return sum;
}
int main()
{
cin >> n >> m;
int x, y, z;
for (int i = 1; i <= m; i++)
{
cin >> x >> y >> z;
//重复的边也进去了
g[x].push_back(node{ y,z });
g[y].push_back(node{ x,z });
}
long long ans = prim(1);
if (ans > maxcost)
cout << "orz" << endl;
else
cout << ans << endl;
}
P2872 [USACO07DEC]Building Roads S
给定 n 个点的坐标给定 m 条边，第 i 条边连接第 ui 个点和第vi 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。
首先循环嵌套枚举求出各个点与其后点的距离。保证只加一次边。在枚举完所有的边的距离之后， 在读入已知边， 这时两点之间的距离直接存为零即可， 表示从i到j的花费为零。然后开始建立最小生成树即可
#include<iostream>
#include<algorithm>
#include <cstring>
#include<cmath>
#include <stdio.h>
using namespace std;
#define maxsize 10005
struct node{int x,y;};
struct edge{int s, e;/*起点终点 */ double w;};
int n, m,num=1;//num边的数量
edge g[1001000];
node spot[maxsize];
int f[maxsize];//记录是否成环，并查集
bool cmp(edge a, edge b){return a.w < b.w;}
int find(int x)
{
if (f[x] == 0 || f[x] == x)
{
f[x] = x;
return x;
}
else
return f[x] = find(f[x]);
}
double ans = 0;
void kruskal()
{
for (int i = 1; i <=num; i++)
{
int x = find(g[i].s);
int y = find(g[i].e);
if (x != y)
{
f[x] = y;
ans +=g[i].w;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> spot[i].x >> spot[i].y;
}
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
g[num].s = i;
g[num].e = j;
g[num++].w = sqrt((double)(spot[i].x - spot[j].x) * (double)(spot[i].x - spot[j].x)
+ (double)(spot[i].y - spot[j].y) * (double)(spot[i].y - spot[j].y));
}
}
int q, w;
for (int i = 1; i <= m; i++)
{
cin >> q >> w ;
g[num].s = q;
g[num].e = w;
g[num++].w = 0.00;
}
sort(g + 1, g + 1 + num, cmp);
kruskal();
printf("%.2lf", ans);//输出
}
P1991 无线通讯网
每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。任意两个配备了一条卫星电话线路的哨所均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。
最小生成树的模板有n - 1条边就可以退出了，这里其它的没变，就退出条件变了，退出条件变成了p - s。有s个卫星电话就是不用连接最大的s-1条边
#include<iostream>
#include<algorithm>
#include <cstring>
#include<cmath>
#include <stdio.h>
using namespace std;
#define maxsize 10005
struct node{int x,y;};
struct edge{int s, e;/*起点终点 */ double w;};
int s, n,num=1;//num边的数量
edge g[1001000];
node spot[maxsize];
int f[maxsize];//记录是否成环，并查集
bool cmp(edge a, edge b){return a.w < b.w;}
int find(int x)
{
if (f[x] == 0 || f[x] == x)
{
f[x] = x;
return x;
}
else
return f[x] = find(f[x]);
}
double ans = 0;
void kruskal()
{
for (int i = 1; i <=num; i++)
{
int x = find(g[i].s);
int y = find(g[i].e);
if (x != y)
{
f[x] = y;
ans = max(ans, g[i].w);
s--;
if (s == 0)
return;
}
}
}
int main()
{
cin >> s >> n;
for (int i = 1; i <= n; i++)
{
cin >> spot[i].x >> spot[i].y;
}
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
g[num].s = i;
g[num].e = j;
g[num++].w = sqrt((double)(spot[i].x - spot[j].x) * (double)(spot[i].x - spot[j].x)
+ (double)(spot[i].y - spot[j].y) * (double)(spot[i].y - spot[j].y));
}
}
s = n - s;
sort(g + 1, g + 1 + num, cmp);
kruskal();
printf("%.2lf", ans);//输出
}
P4047 [JSOI2010]部落划分
我们把每个点看成一个部落，每次取最小距离的两个抱团，同时部落也减少了一个…然后减减减，直到部落数==目标数，此时下一个不同部落的距离就是最短的距离！
我们把每个点看成一个部落，每次取最小距离的两个抱团，同时部落也减少了一个…然后减，直到部落数==目标数，此时下一个不同部落的距离就是最短的距离！
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxsize 900010
int f[maxsize];
struct edge { int s, e;/*起点终点 */ double w; };
struct position { int x, y; };
edge g[maxsize];
position h[maxsize];
bool cmp(edge a, edge b) { return a.w < b.w; }
int find(int x)
{
if (f[x] == x || f[x] == 0)
{
f[x] = x;
return f[x];
}
else
return f[x] = find(f[x]);
}
int main()
{
int n, m=1,k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> h[i].x >> h[i].y;
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
double w = (double)sqrt((h[i].x - h[j].x) * (h[i].x - h[j].x) + (h[i].y - h[j].y) * (h[i].y - h[j].y));
g[m++] = edge{ i,j,w};
}
}
sort(g + 1, g + m, cmp);
int ans = 0;
int flag = 0;
for (int i = 1; i < m; i++)
{
int x = find(g[i].s);
int y = find(g[i].e);
if (ans == n - k)
flag = 1;
if (x != y)
{
f[x] = y;
ans++;
if (flag)//是要在里面 不同的距离
{
printf("%0.2lf\n", g[i].w);
break;
}
}
}
}
P1396 营救
该市有 m 条大道连接 n 个区，一条大道将两个区相连接，每个大道有一个拥挤度。请你帮她规划一条从 s 至 t 的路线，使得经过道路的拥挤度最大值最小。
将边从小到大排序,然后最小生成树连边,这样当s和t第一次联通时,当前边的权值就是答案了。
#include<iostream>
#include<algorithm>
#include <cstring>
using namespace std;
#define maxsize 20010
int n, m, s, t;
struct edge{int x, y, w;/*起点终点权值*/}g[maxsize];
int num = 0;
bool cmp(edge a, edge b) { return a.w < b.w; }
int f[maxsize];
int find(int x)
{
if (f[x] == 0 || f[x] == x)
{
f[x] = x;
return x;
}
else
return f[x] = find(f[x]);
}
int main()
{
cin >> n >> m >> s >> t;
int x, y, w;
for (int i = 1; i <= m; i++)
{
cin >> x >> y >> w;
g[num++] = edge{ x,y,w };
}
sort(g, g + num, cmp);
for (int i = 0; i < num; i++)
{
x = find(g[i].x);
y = find(g[i].y);
if (x != y)
f[x] = y;
if (find(s) == find(t))
{
cout << g[i].w << endl;
break;
}
}
}
P2121 拆地毯
会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示，其中 u 和 v 为地毯连接的两个关键区域编号，w 为这条地毯的美丽度。，只能保留 K 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。算出这 K 条地毯的美丽度之和最大为多少。
拆地毯,让我们剩下k个,因此我们合并出k个即可，构造出最大生成树。
#include<iostream>
#include<algorithm>
#include <cstring>
#include<cmath>
using namespace std;
#define maxsize 100010
int n, m, k;
struct edge{int x, y, w;/*起点终点权值*/}g[maxsize];
int num = 0;
bool cmp(edge a, edge b) { return a.w > b.w; }
int f[maxsize];
int find(int x)
{
if (f[x] == 0 || f[x] == x)
{
f[x] = x;
return x;
}
else
return f[x] = find(f[x]);
}
int main()
{
cin >> n >> m >>k;
int x, y, w;
for (int i = 1; i <= m; i++)
{
cin >> x >> y >> w;
g[num++] = edge{ x,y,w };
}
sort(g, g + num, cmp);
long int cnt = 0,ans=0;
for (int i = 0; i < num; i++)
{
x = find(g[i].x);
y = find(g[i].y);
if (x != y)
{
f[x] = y;
cnt++;
ans += g[i].w;
}
if (cnt ==k)
break;
}
cout << ans << endl;
}
P1194 买礼物
如果你买了第I样东西，再买第J样，那么就可以只花K（i，j）元，更巧的是，K（i，j）竟然等于K（j，i），如果为0则表示不优惠。
那么可以算优惠掉了多少钱（代表权值），求出最大的生成树，将权值相加，最后原件减去优惠掉的钱就是优惠后要花的钱数。
#include<iostream>
#include<algorithm>
#include <vector>
#include <cstring>
#include<cmath>
using namespace std;
#define maxsize 100010
int f[maxsize];
struct edge { int s, e, w; };
struct position { int x, y; };
edge g[maxsize];
bool cmp(edge a, edge b) { return a.w > b.w; }
int find(int x)
{
if (f[x] == x || f[x] == 0)
{
f[x] = x;
return f[x];
}
else
return f[x] = find(f[x]);
}
int main()
{
int a, b,num=1;
cin >> a >> b;
int x, y, w;
for (int i = 1; i <= b; i++)
{
for (int j = 1; j <= b; j++)
{
cin >> w;
if (w != 0&&i<=j&&w<a)//边只存一次
g[num++] = { i,j,a-w };//存便宜的钱
}
}
int ans = 0,n=0;//优惠的钱,次数
sort(g + 1, g + num, cmp);
for (int i = 1; i <= num; i++)
{
int x = find(g[i].e);
int y = find(g[i].s);
if (x != y)
{
f[x] = y;
ans += g[i].w;
}
}
cout << a * b - ans << endl;
}
P1195 口袋的天空
给你云朵的个数N ，再给你M 个关系，表示哪些云朵可以连在一起。现在小杉要把所有云朵连成K个棉花糖，一个棉花糖最少要用掉一朵云，怎么连，花费的代价最小。
如果n个点被n-1条边连接的话，这一定是棵树。所以我们如果想要连出k棵树，就需要连n-k条边。那么当然要选择代价最小的边连起来。所以给每条可以连的边按代价从小到大排个序，然后连n-k条边造k个最小生成树就可以了。
#include<iostream>
#include<algorithm>
using namespace std;
#define maxsize 100010
int f[maxsize];
struct edge { int s, e;/*起点终点 */ double w; };
edge g[maxsize];
bool cmp(edge a, edge b) { return a.w < b.w; }
int find(int x)
{
if (f[x] == x || f[x] == 0)
{
f[x] = x;
return f[x];
}
else
return f[x] = find(f[x]);
}
int main()
{
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
cin >> g[i].s >> g[i].e >> g[i].w;
sort(g + 1, g + 1 + m, cmp);
int ans = 0;
int edge_num = 0;//边数
for (int i = 1; i <= m; i++)
{
int x = find(g[i].s);
int y = find(g[i].e);
if (x != y)
{
f[x] = y;
ans += g[i].w;
edge_num++;
}
if (edge_num>=n-k)
break;
}
if (edge_num < n - k)
cout << "No Answer" << endl;
else
cout << ans << endl;
}
本文地址：https://blog.csdn.net/weixin_45605341/article/details/107833298
上一篇： HDU多校三