fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. struct edges
  6. {
  7.     ll val,u,v;
  8.     edges(){}
  9.     edges(ll _val,ll _u,ll _v)
  10.     {
  11.         val=_val;
  12.         u=_u;
  13.         v=_v;
  14.     }
  15. };
  16.  
  17. bool cmp(edges a,edges b)
  18. {
  19.     if(a.val<b.val)return 1;
  20.     return 0;
  21. }
  22.  
  23. vector<edges>edge,edge2;
  24. vector<pair<ll,ll> >ans;
  25. ll tes;
  26. ll n,m,arr[1005];
  27. ll degree[1005];
  28.  
  29. int main()
  30. {
  31.     scanf("%lld",&tes);
  32.     for(ll cas=1;cas<=tes;cas++)
  33.     {
  34.         edge.clear();
  35.         edge2.clear();
  36.         ans.clear();
  37.         scanf("%lld %lld",&n,&m);
  38.         for(ll i=1;i<=n;i++){scanf("%lld",&arr[i]);degree[i]=0;}
  39.         for(ll i=1;i<=n;i++)
  40.         {
  41.             for(ll j=i+1;j<=n;j++)
  42.             {
  43.                 edge.push_back(edges(arr[i]+arr[j],i,j));
  44.             }
  45.         }
  46.         sort(edge.begin(),edge.end(),cmp);
  47.  
  48.  
  49.  
  50.         bool f=0;
  51.         ll ans2=0;
  52.  
  53.         for(ll i=0;i<edge.size();i++)
  54.         {
  55.             ll u=edge[i].u;
  56.             ll v=edge[i].v;
  57.  
  58.             if(degree[u]<2 && degree[v]<2)
  59.             {
  60. //                cout<<u<<" "<<v<<endl;
  61.                 if(m>0)
  62.                 {
  63.                     m--;
  64.                     ans.push_back(make_pair(u,v));
  65.                     degree[u]++;
  66.                     degree[v]++;
  67.                     ans2+=edge[i].val;
  68.                 }
  69.                 else {f=1;break;}
  70.             }
  71.             else edge2.push_back(edge[i]);
  72.         }
  73. //        cout<<m<<endl;
  74.  
  75.  
  76.         if(f){printf("-1\n");continue;}
  77.  
  78.         sort(edge2.begin(),edge2.end(),cmp);
  79.         reverse(edge2.begin(),edge2.end());
  80.  
  81.         while(m>0 && edge2.size()>0)
  82.         {
  83.             ans2+=edge2[edge2.size()-1].val;
  84.             ans.push_back(make_pair(edge2[edge2.size()-1].u,edge2[edge2.size()-1].v));
  85.             edge2.pop_back();
  86.             m--;
  87.         }
  88.  
  89.         while(m>0)
  90.         {
  91.             ans2+=edge[0].val;
  92.             ans.push_back(make_pair(edge[0].u,edge[0].v));
  93.             m--;
  94.         }
  95.  
  96.         cout<<ans2<<endl;
  97.         for(ll i=0;i<ans.size();i++)
  98.         {
  99.             printf("%lld %lld\n",ans[i].first,ans[i].second);
  100.         }
  101.     }
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/d0w6w5
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!