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