【codeforces 782C】Andryusha and Colored Balloons

2019-11-06 06:50:42

字体：大中小

来源：转载

供稿：网友

【题目链接】:http://codeforces.com/contest/782/PRoblem/C

【题意】给你一棵树让你满足要求 ->任意相连的3个节点的颜色不能相同的情况下进行染色问最少需要的颜色数目

【题解】这种染色题一般只要贪心染就好了即之前没出现过的颜色最小的颜色就好; (这里的之前指的是当前枚举的节点和它的父亲节点以及这个节点的儿子节点们。。) 感觉很多题都要顺着题意去做啊; 【完整代码】

#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int, int> pii;typedef pair<LL, LL> pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };const double pi = acos(-1.0);const int N = 2e5+1000;vector <int> G[N];int n;int color[N];void dfs(int x, int fa){ int now = 0; for (int y : G[x]) if (y!=fa) { now++; while (color[fa] == now || color[x] == now) now++; color[y] = now; dfs(y, x); }}int main(){ //freopen("F://rush.txt", "r", stdin); rei(n); rep1(i, 1, n - 1) { int x, y; rei(x), rei(y); G[x].push_back(y), G[y].push_back(x); } color[1] = 1; dfs(1, -1); printf("%d/n", color[max_element(color + 1, color + 1 + n)-color]); rep1(i, 1, n) printf("%d ", color[i]); return 0;}

上一篇：matlab下关于将原图和检测结果图合成半透明效果

下一篇：“玲珑杯”ACM比赛 Round #11