题目

4、regional link（district）–1200
时间限制： | 空间限制：
题目描述：
有 个点,第 The color of a dot is .
你要添加 A bidirectional edge connects all points.The two endpoints of an edge cannot have the same color.
Give any constructive scheme that meets the conditions,Or judge that there is no eligible scheme.共 组数据.
输入格式：
第一行仅有一个正整数 （ ）,表示测试数据的组数.
每组测试数据包括两行：
第一行一个正整数 （ ,所有数据中 之和不超过 ）,表示点的个数;
第二行 个正整数 （ ）,表示每个点的颜色.
输出格式：
对于每组测试数据,If there is no matching scheme output ;
否则,第一行输出 ,接下来的 The line outputs the endpoints of each edge in your construction scheme.

思路

将nThe records of all legal unvisited points that can be connected to one point will continue to traverse the remaining points

重点

Time complexity is only supportedO(n^2),合理控制

代码实现

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e3+10;
int t,n;
int a[maxn];
int mp[maxn][2];
bool vis[maxn];
inline bool Prim(){
    
	memset(vis,false,sizeof(vis));
	memset(mp,0,sizeof(mp));
	vis[1]=true;
	int cnt=0;
	for(int i=1;i<=n;i++){
    
		if(!vis[i])continue;
		for(int j=1;j<=n;j++){
    
			if(vis[j])continue;
			if(a[i]==a[j])continue;
			mp[++cnt][0]=i;
			mp[cnt][1]=j;
			vis[j]=true;
		}
	}
	bool flag=true;
	for(int i=1;i<=n;i++){
    
		if(!vis[i]){
    
			flag=false;
			break;
		}
	}
	if(flag)return true;
	return false;
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		if(Prim()){
    
			printf("YES\n");
			for(int i=1;i<=n-1;i++)printf("%d %d\n",mp[i][0],mp[i][1]);
		}
		else printf("NO\n");
	}
	return 0;
}