Codeforces Round #677 D. Districts Connection

迈不过友情╰ 2021-07-16 18:57 275阅读 0赞

[题目][Link 1]

题意：给出n个点，对n个点连n-1条边要求构成一棵树，其中对于树中属于同一帮派的点不能相互连边。则我们只需对所有的点进行连边尝试，直到连了n-1条边即可。遇到同一个帮派的点或已经连接的点直接跳过即可。(题目数据不大直接暴力就过了)

AC code

#include<iostream>
        #include<string>
        #include<map>
        #include<algorithm>
        #include<memory.h>
        #include<cmath>
        #define pii pair<int,int>
        #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
        using namespace std;
        typedef long long ll;
        const int Max = 1e6 + 5;
        int lst[Max];
        int ls[Max][2];
         
        int main()
        { 
        	FAST;
        	int t;cin >>t;
        	while (t--)
        	{ 
        		map<int, int> ma;//ma用来标记哪些点已经连接
        		int n;cin >> n;
        		for (int i = 1;i <= n;i++)cin >> lst[i];
        		int g = 0;
        		for (int i = 1;i <= n;i++)
        		{ 
        			for (int j = 1;j <= n;j++)
        			{ 
        				if (g == n - 1)break;//已连n-1条边
        				if (ma[i]&&ma[j])//两点已在
        				{ 
        					continue;
        				}
        				else
        				{ 
        					if (lst[i] == lst[j])continue;//相同帮派跳过
        					else
        					{ 
        						ma[i]++,ma[j]++;
        						ls[++g][0] = i, ls[g][1] = j;
        					}
        				}
        			}
        		}
        		if (g != n - 1)
        			cout << "NO" << endl;
        		else
        		{ 
        			cout << "YES" << endl;
        			for (int i = 1;i <= g;i++)cout << ls[i][0] << " " << ls[i][1] << endl;
        		}
        		
        	}
        }

[Link 1]: https://codeforces.ml/contest/1433/problem/D