题目链接：

题意：

给定n个点 m条边的无向图 须要在图里添加p条边 使得图最后连通分量数为q

问是否可行，不可行输出NO

可行输出YES，并输出加入的p条边。

set走起。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define N 123456#define ll __int64ll n,m,p,q;struct Edge{ ll from, to, dis;}edge[N*2];ll edgenum;void add(ll u,ll v,ll dis){ Edge E={u,v,dis}; edge[edgenum++] = E;}ll f[N];ll find(ll x){return x==f[x]?x:f[x]=find(f[x]);}void Union(ll x,ll y){ ll fx = find(x), fy = find(y); if(fx==fy)return ; if(fx
           
            myset;set
            
             ::iterator pp;ll siz[N];vector
             
              L,R;struct node{ ll fa, val; bool operator<(const node&x)const{ if(x.val==val)return x.fa
              
               val; } node(ll x=0,ll y = 0):fa(x),val(y){}};set
               
                hehe;set
                
                 ::iterator dd;void init(){ hehe.clear(); L.clear(); R.clear(); memset(siz, 0, sizeof siz); myset.clear(); for(ll i = 1; i <= n; i++)f[i]=i; edgenum = 0;}void go(){ dd = hehe.begin(); node x = *dd; hehe.erase(dd); dd = hehe.begin(); node y = *dd; hehe.erase(dd); Union(x.fa,y.fa); ll now = min((ll)1000000000, x.val+y.val+1); node z = node(find(x.fa),x.val+y.val+now); hehe.insert(z); L.push_back(x.fa); R.push_back(y.fa); add(x.fa,y.fa,1);}int main(){ ll i, j, u, v, d; while(~scanf("%I64d %I64d %I64d %I64d",&n,&m,&p,&q)){ init(); while(m--){ scanf("%I64d %I64d %I64d",&u,&v,&d); add(u,v,d); Union(u,v); } for(i = 1; i <= n; i++)find(i); for(i = 1; i <= n; i++)myset.insert(f[i]); for(i = 0; i < edgenum; i++){ siz[f[edge[i].from]]+=edge[i].dis; } if(myset.size()
                 
                  p){puts("NO");continue;} p-=ned; for(pp=myset.begin(); pp!=myset.end(); pp++)hehe.insert(node(*pp,siz[*pp])); while(ned--)go(); puts("YES"); for(i = 0; i < L.size(); i++)cout<
                  
                   <<" "<
                   
                    <