Fools and Foolproof Roads CodeForces - 362D

2019-11-06 06:36:35

字体：大中小

来源：转载

供稿：网友

题目链接

大意：给出一个图，n个点，m条边，想要修p条路，使得图的连通分量是q；如果满足要求，就输出p条路,并且使得花费最小

思路：使用并查集来做，并使用了一个len数组来记录每一个连通分量里面总的路线长度, now ->原图的连通分量,q>now的时候直接输出NO，否则如下表讨论

条件	结果
now-q>q	NO
p>=now-q && m!=0	YES
p>=now-q m==0 && q!=0	NO
p>=now-q m==0 && q==0	YES

#include <iostream>#include <cstdio>#include <set>#include <algorithm>#include <queue>using namespace std ;typedef long long LL ;const int maxn = 1e5+5 ;struct node { int index; long long value; node ( int x,long long y ) { index = x; value = y; } bool Operator < ( const node &a ) const { if ( value==a.value ) return index<a.index; return value<a.value; }};int f[maxn];long long len[maxn];int find( int x) { return f[x]==x?x:find(f[x]); }vector<int> L;vector<int> R;set<node> s;set<node>::iterator sit;void solve() { sit = s.begin(); node a1 = *sit; s.erase(sit); sit = s.begin(); node a2 = *sit; s.erase(sit); LL temp = min( (long long)10e9,a2.value+a1.value+1 ) ; //!!!!!!!!! L.push_back(a1.index); R.push_back(a2.index); s.insert(node( a1.index , temp+a2.value+a1.value)); return ;}void init( int n ) { for ( int i=1; i<=n; i++ ) f[i] = i ;}int main(){ int n,m,p,q; int a,b,c; int fa,fb,fc; int ned=0,ned2=0; cin>>n>>m>>p>>q; init(n); for ( int l=0; l<m; l++ ) { scanf("%d%d%d",&a,&b,&c); fa = find(a); fb = find(b); if ( fa==fb ) len[fa] += c; else { f[fa] = fb; len[fb] += len[fa] + c ; } } for ( int i=1; i<=n ; i++ ) { if ( f[i]==i ) { s.insert(node(i,len[i])); } } if ( s.size()<q ) cout<<"NO"<<endl; else { if ( p+q<s.size() ) cout<<"NO"<<endl; else { if ( s.size()==q && m==0 &&p!=0 ) cout<<"NO"<<endl; //特别注意的情况 else { ned = s.size()-q; ned2 = p-ned; for ( int i=0; i<ned; i++ ) solve(); cout<<"YES"<<endl; for ( int i=0; i<ned; i++ ) cout<<L[i]<<" "<<R[i]<<endl; if ( m==0 ) { a = 1;b=2; } while ( ned2-- ) { cout<<a<<" "<<b<<endl; } } } } return 0;}

上一篇：Spring(四、Spring整合hibernate）

下一篇：Add Two Numbers

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注