noip2019集训测试赛（十一）A.管道（pipe）

本文主要是介绍noip2019集训测试赛（十一）A.管道（pipe），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给你一个城市下水道网络图，你需要选出一些管道，使得在只使用这些管道的情况下，令整个网络联通，并且花费最小。

网络图可以看做是无向连通图，有n个节点和m条边，每条边连接ui和vi，选择的花费是wi。

不巧的是，由于某些原因，现在市政局要求选定某条特定的边管道，你的任务是求出对于某一条边，在选择这条管道的前提下的最小花费。

Input

第1行包含两个整数n，m，表示点数和边数。

第2~m+1行每行三个整数ui，vi，wi，表示有一条管道连接ui和vi，费用为wi。

Output

输出m行，每行一个整数，表示选择第i条管道的前提下的最小花费。

管道按输入的顺序编号为1~m。

Solution

看到题面就想起之前的一道题MST
题解链接：https://blog.csdn.net/tylon2006/article/details/100023009

MST是分为两个部分处理答案，其中第一个部分算出了该边所在环上树边边权上的最大值。

而本题我们要求的就是使用该边替换最大值边得到的花费，将原最小生成树边权和加上该边边权再减去最大值即可。

注意：本题未给出数据范围，但要开long long，否则当场挂零

Code

#include<bits/stdc++.h> 
using namespace std;
int n,m,cnt=0;
int head[200010];
long long ans[200010],res;
int fa[200010],dep[200010],id[200010];
int f[200010][20];
long long maxn[200010][20];
bool vis[200010];
struct data{int x,y,id;long long dis;bool operator <(const data &a)const{return dis<a.dis;} 
}a[200010];
struct edge{int x,dis,nxt,id;
}e[400010];
inline void add(int x,int y,int z,int id){e[++cnt].x=y;e[cnt].dis=z;e[cnt].id=id;e[cnt].nxt=head[x];head[x]=cnt;
}
int find(int x){if(fa[x]==x) return fa[x];return fa[x]=find(fa[x]);
}
void build(){sort(a+1,a+m+1);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++){int x=a[i].x,y=a[i].y;int fx=find(x),fy=find(y);if(fx!=fy){fa[fy]=fx;vis[a[i].id]=true;add(x,y,a[i].dis,a[i].id);add(y,x,a[i].dis,a[i].id);res+=a[i].dis;}}
}
void dfs(int x){for(int i=1;i<=18;i++){f[x][i]=f[f[x][i-1]][i-1];maxn[x][i]=max(maxn[x][i-1],maxn[f[x][i-1]][i-1]);}for(int i=head[x];i;i=e[i].nxt)if(e[i].x!=f[x][0]){f[e[i].x][0]=x;id[e[i].x]=e[i].id;dep[e[i].x]=dep[x]+1;maxn[e[i].x][0]=e[i].dis;dfs(e[i].x);}
}
long long get(int x,int y,int &lca){long long ans=0;if(dep[x]<dep[y]) swap(x,y);for(int i=18;i>=0;i--)if(dep[f[x][i]]>=dep[y]){ans=max(ans,maxn[x][i]);x=f[x][i];}if(x==y){lca=x;return ans;}for(int i=18;i>=0;i--){if(f[x][i]!=f[y][i]){ans=max(ans,maxn[x][i]);ans=max(ans,maxn[y][i]);x=f[x][i],y=f[y][i];}}lca=f[x][0];return max(ans,max(maxn[x][0],maxn[y][0]));
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].dis);ans[i]=2e9; a[i].id=i;}build(),dfs(1);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++)if(!vis[a[i].id]){int x=a[i].x,y=a[i].y,z;ans[a[i].id]=res+a[i].dis-get(x,y,z);}for(int i=1;i<=m;i++){if(ans[i]==2e9) printf("%lld\n",res);else printf("%lld\n",ans[i]);}
}