题意： 给出一些节点，每个节点有权值，权值相同的节点不能相连，问是否有办法使用n-1条边将所有节点连成连通图。如果可以，输出路径。不可以输出NO即可。 题解： 只要有不同的必定有答案 只需要将所有与第一个不同的与第一个相连 再将剩下的与其他任意一个相连即可 比赛没做出来，人傻了 code:
#include<bits/stdc++.h> using namespace std; int a[5010],vis[5010]; void solve(){ int n; cin>>n; memset(vis,0,sizeof(vis)); int f=0; for(int i=1;i<=n;i++){ cin>>a[i]; if(i!=1&&a[i]!=a[1]){ f=1; vis[i]=1; } } if(!f) cout<<"NO"<<endl; else { cout<<"YES"<<endl; int pos; for(int i=1;i<=n;i++){ if(vis[i]) pos=i,cout<<1<<" "<<i<<endl; } for(int i=1;i<=n;i++){ if(!vis[i]&&i!=1) cout<<pos<<" "<<i<<endl; } } } int main(){ int t; cin>>t; while(t--) solve(); }