【BZOJ 4878】[Lydsy2017年5月月赛] 挑战NP-Hard

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4878

解题报告

我们搞出$DFS$生成树
如果树高大于$k$,那么显然可以找出长度为$k$的简单路径
如果树高$\le k$的话,因为非树边一定是返祖边,所以把深度作为颜色就可以$k$染色了

Code

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

const int N = 1009;
const int M = 20009;

int n,m,k,E,head[N],nxt[M],to[M];
int DONE,fa[N],dep[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w, int f) {
	dep[w] = dep[f] + 1;
	fa[w] = f;
	if (dep[w] > k) {
		DONE = 1;
		printf("path ");
		for (; 1; w = fa[w]) {
			printf("%d ", w);
			if (w == fa[w]) {
				break;
			}
		}
		cout<<endl;
	} else {
		for (int i = head[w]; i && !DONE; i = nxt[i]) {
			if (!dep[to[i]]) {
				DFS(to[i], w);
			}
		}
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	for (int T = read(); T; T--) {
		memset(head, 0, sizeof(head));
		n = read(); m = read(); 
		k = read(); E = DONE = 0;
		for (int i = 1; i <= m; i++) {
			AddEdge(read(), read());
		}
		memset(dep, 0, sizeof(dep));
		for (int i = 1; i <= n && !DONE; ++i) {
			if (!dep[i]) {
				DFS(i, i);
			}
		}
		if (!DONE) {
			printf("color ");
			for (int i = 1; i <= n; ++i) {
				printf("%d ", dep[i]);
			}
			cout<<endl;
		}
	} 
	return 0;
}

2 thoughts to “【BZOJ 4878】[Lydsy2017年5月月赛] 挑战NP-Hard”

  1. I discovered your blog site on google and check a few of your early posts. Continue to keep up the very good operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading more from you later on!…

  2. I just couldn’t depart your website prior to suggesting that I really enjoyed the standard info a person provide for your visitors? Is gonna be back often to check up on new posts

Leave a Reply

Your email address will not be published. Required fields are marked *