当前位置:网站首页>AcWing 1148. Secret milk transportation problem solution (minimum spanning tree)
AcWing 1148. Secret milk transportation problem solution (minimum spanning tree)
2022-07-07 01:36:00 【Mr. Qiao Da】
AcWing 1148. Secret milk transport
Their thinking : First find the minimum spanning tree , Calculate the sum of the weights and mark all the edges in the minimum spanning tree . Then traverse all edges , Find the largest edge and the second largest edge on the path containing two points and record ,( When two points find a new path to connect , Only which largest side is disconnected (t = sum - dist1[a][b] + w,dist1 Is the largest edge , It is concluded that the t Will be a smaller value , Then we can get the second smallest spanning tree ), To ensure that the next small spanning tree is found , So record the largest edge , The second largest edge is recorded to prevent the largest edge from being used ), Then traverse all the edges in the non minimum spanning tree , Replace the edges in the tree in turn , Finally, we find the second smallest spanning tree
Big guy problem solving original address
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510, M = 2e4 + 10;
int n, m;
int p[N]; // Union checking set
int dist1[N][N], dist2[N][N]; // Record the maximum value and the second maximum value on the corresponding edge path respectively
ll res = 1e18; // The final answer
ll sum; // Record the weight of the minimum spanning tree
int h[N], e[M], ne[M], w[M], idx; // Record tree
struct Edge{
int a, b, w;
bool f; // Mark whether this edge is in the minimum spanning tree
bool operator< (const Edge &t) const {
return w < t.w;
}
}edg[M];
void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++ ;
}
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void dfs(int u, int fa, int mad1, int mad2, int d1[], int d2[]){
// Find the maximum value and the second largest value on the path corresponding to each point
d1[u] = mad1, d2[u] = mad2; //d1、d2 Array has no assignment before
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j != fa){
int td1 = mad1, td2 = mad2;
if(w[i] > td1){
td2 = td1;
td1 = w[i];
}
else if(w[i] < td1 && w[i] > td2){
td2 = w[i];
}
dfs(j, u, td1, td2, d1, d2);
}
}
}
signed main()
{
cin>>n>>m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++ ){
int a, b, c;
cin>>a>>b>>c;
edg[i] = {
a, b, c};
}
// Find the smallest spanning tree
sort(edg, edg + m);
for(int i = 1; i <= n; i ++ ) p[i] = i;
for(int i = 0; i < m; i ++ ){
int a = edg[i].a, b = edg[i].b, w = edg[i].w; // Here we need to use points to build maps , therefore a、b Are used to express themselves
int pa = find(a), pb = find(b);
if(pa != pb){
sum += w;
p[pa] = pb;
add(a, b, w);
add(b, a, w);
edg[i].f = true;
}
}
// Find the maximum value and the second largest value of the path corresponding to each point
for(int i = 1; i <= n; i ++ ) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);
for(int i = 0; i < m; i ++ ){
if(!edg[i].f){
int a = edg[i].a, b = edg[i].b, w = edg[i].w;
ll t;
if(w > dist1[a][b]){
t = sum - dist1[a][b] + w;
}
else if(w > dist2[a][b]){
t = sum - dist2[a][b] + w;
}
res = min(res, t);
}
}
cout<<res<<endl;
return 0;
}
边栏推荐
- AcWing 904. 虫洞 题解(spfa求负环)
- Share a general compilation method of so dynamic library
- 第三方跳转网站 出现 405 Method Not Allowed
- Match VIM from zero (0) -- Introduction to vimscript
- Appium自动化测试基础 — uiautomatorviewer定位工具
- Neon Optimization: performance optimization FAQ QA
- tansig和logsig的差异,为什么BP喜欢用tansig
- 糊涂工具类(hutool)post请求设置body参数为json数据
- 新工作感悟~辞旧迎新~
- 7.6模拟赛总结
猜你喜欢
How to manage distributed teams?
新工作感悟~辞旧迎新~
2022 Google CTF segfault Labyrinth WP
Instructions for using the domain analysis tool bloodhound
[advanced C language] 8 written questions of pointer
子网划分、构造超网 典型题
Appium foundation - appium inspector positioning tool (I)
Transformation transformation operator
AI 从代码中自动生成注释文档
Typical problems of subnet division and super network construction
随机推荐
Taro2.* 小程序配置分享微信朋友圈
How to prevent overfitting in cross validation
C语言实例_3
C language - array
交叉验证如何防止过拟合
[signal and system]
Neon Optimization: performance optimization FAQ QA
百度飞将BMN时序动作定位框架 | 数据准备与训练指南 (下)
Body mass index program, entry to write dead applet project
修改px4飞控的系统时间
Typical problems of subnet division and super network construction
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
AcWing 344. 观光之旅题解(floyd求无向图的最小环问题)
Set up [redis in centos7.x]
Gin 入门实战
AcWing 345. 牛站 题解(floyd的性质、倍增)
Appium自动化测试基础 — uiautomatorviewer定位工具
THREE.AxesHelper is not a constructor
Wood extraction in Halcon
Neon Optimization: an instruction optimization case of matrix transpose