Codeforces Round #677 (Div. 3) D. Districts Connection思维1200

题目链接 Problem - 1433D - Codeforces

 

题目

美好的一天,从看不懂题目开始~~

Codeforces Round #677 (Div. 3) D. Districts Connection思维1200

 

Example input
4
5
1 2 2 1 3
3
1 1 1
4
1 1000 101 1000
4
1 2 3 4

 

output
YES
1 3
3 5
5 4
1 2
NO
YES
1 2
2 3
3 4
YES
1 2
1 3
1 4

 

 

 

题意

给n个区域,用n-1个路把它们连起来,使每个地方都能到达其它任何地方

但是呢,每个区域都属于一个组织,不能让两个相同的组织直接相连

 

解析

想到了就很容易过的,比如说拿1当中介,所有的与1不同组织的区域都和1相连,与1同组织的与temp相连

其中temp=“和1非同组织的序号”

 

 

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

int a[5010];

int main()
{
   int t;
   cin >> t;
   while(t --)
   {
       int n;
       cin >> n;
       int lag = 0;
       for(int i = 1; i <= n; i ++) 
       {
            cin >> a[i];
            if(i!= 1 && a[i] != a[1]) 
                lag = i;
       }
       if(lag==0)
        cout << "NO" << endl;
       else
       {
           cout << "Yes" << endl;
           for(int i = 2; i <= n; i ++)
                if(a[i] != a[1])
                    cout << 1 << ' ' << i << endl;
                else cout << i << ' '<< lag << endl;
       } 
   }
    return 0;
}

 

 

英语小芝士

district  区域,地方

distinct 不同的,清楚的,明显的

gang  伙,群

输出部分的:

   Each road should be presented as a pair of integers xi and yi (1≤xi,yi≤n;xi≠yi1≤xi,yi≤n;xi≠yi), where xi and yi are two districts the ii-th road connects.

   每条路都应该用一对整数xi,yi表示, xi,yi是不同的区域

上一篇:M-LAG-2


下一篇:在计量实证中常见操作问题小结,计量经济圈专刊