如何粘贴网站统计代码/谷歌浏览器手机版

H

题意：
给你n个点，m条边，问你如果只让这个树拥有一个唯一的最小生成树。那么要删去的边的权值和最小为多少。

思考：
刚开始我以为是先把最小生成树的权值和删去，然后剩下的边如果还能组成再删啥的，但是这样太不全面了，所以是不对的。其实可以按边权来，当边权相同的一些边，他们的地位都是一样的，那么他们代表的点如果不在一个集合就可能成为最小生成树的边，所以这样就不唯一了。因此只要把能进去的都加上，最后再减去最小生成树的边权和就是答案。
以前做过类似的一道题MST+1，那个题目也是说n点m边，问你每一条边，是否可能成为最小生成树的一条边。所以啊，那题也是对于权值相同的边也就是地位相同的，都可以进去，然后再去合并就行了。

代码：

本题代码：struct Node{int a,b,c;
}node[N];int T,n,m,k;
int ans,sum;
int va[N];
int acc[N];map<int,vector<Node> > mp;bool cmp(Node a,Node b)
{return a.c<b.c;
}int find(int x)
{if(x!=acc[x]) acc[x] = find(acc[x]);return acc[x];
}void krukal()
{for(auto t:mp){for(auto tt:t.se){int a = tt.a,b = tt.b,c = tt.c;int t1 = find(a),t2 = find(b);if(t1!=t2) ans += c;}for(auto tt:t.se){int a = tt.a,b = tt.b,c = tt.c;int t1 = find(a),t2 = find(b);if(t1!=t2){acc[t1] = t2;sum += c;}}}
}signed main()
{IOS;cin>>n>>m;for(int i=1;i<=n;i++) acc[i] = i;for(int i=1;i<=m;i++)  {int a,b,c;cin>>a>>b>>c;node[i] = {a,b,c};mp[c].pb(node[i]);}krukal();cout<<ans-sum;return 0;
}MST+1代码：struct node{int a,b,c;int id;
};int T,n,m,k;
node va[N];
int vis[N];
int acc[N];
map<int,vector<node> > mp;bool cmp(node A,node B)
{return A.c<B.c;
}int find(int x)
{if(x!=acc[x]) acc[x] = find(acc[x]);return acc[x];
}void krukal()
{for(int i=1;i<=n;i++) acc[i] = i;for(auto now:mp){for(auto t:now.se){int a = t.a,b = t.b,c = t.c,id = t.id;int t1 = find(a),t2 = find(b);if(t1!=t2) vis[id] = 1;}for(auto t:now.se){int a = t.a,b = t.b,c = t.c,id = t.id;int t1 = find(a),t2 = find(b);if(t1!=t2) acc[t1] = t2;}}
}signed main()
{IOS;cin>>n>>m>>k;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;mp[c].pb({a,b,c,i});}for(int i=m+1;i<=m+k;i++){int a,b,c;cin>>a>>b>>c;mp[c].pb({a,b,c,i});}krukal();for(int i=m+1;i<=m+k;i++){if(vis[i]) cout<<"Yes\n";else cout<<"No\n";}return 0;
}

总结：
多多思考，一定要认真研究和理解。