毁灭PTA
思路:
一道比较简单的最小生成树的应用,因为他的边权存在负值,而我们又想要得到最大分数,事实上我们就只需要统计一下正数的总和以及我们在建树时候用到了多少正数边权就可以巧妙地解决这个问题
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int fa[N];
struct node
{
int a,b,c;
}f[N];
int n,m;
void init(){
for(int i=1;i<=N;i++){
fa[i]=i;
}
}//并查集的初始化
int find(int x){//并查集的查找与合并
if(fa[x]==x){
return x;
}
else{
return fa[x]=find(fa[x]);
}
}
bool cmp(node x,node y){
return x.c<y.c;
}
void solve(){
init();//初始化
cin>>n>>m;
// int l=1;
int sum=0;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
if(w>0){
sum+=w;
}
f[i]={u,v,w};
}
int cnt=0;
int res=0;
sort(f+1,f+m+1,cmp);
for(int i=1;i<=m;i++){
auto it=f[i];
int x1=it.a;
int y1=it.b;
if(find(x1)!=find(y1)){
fa[find(x1)]=fa[find(y1)];
cnt++;//边数加
if(it.c>0){
res+=it.c;
}
}
}
// cout<<cnt<<" "<<res<<endl;
// return ;
//最小生成树一定是只有n-1条边
//虽然我们建好树了,但是有些边其实也可以不用被毁掉,不然得分还是会少
cout<<sum-res<<endl;
return ;
}
signed main(){
int t=1;
while(t--){
solve();
}
return 0;
}
标签:int,res,边权,毁灭,long,PTA
From: https://www.cnblogs.com/du463/p/17865272.html