[BZOJ1006][[HNOI2008]神奇的国度][MCS，完美消除序列]

2019-11-06 07:59:16

字体：大中小

来源：转载

供稿：网友

[BZOJ1006][[HNOI2008]神奇的国度][MCS，完美消除序列]

题目大意：

对给定的N<=10000 $N<=10000$ 个点M<=1000000 $M<=1000000$ 条边的弦图染色，使得两两相邻的点颜色不能相同，求最小需要的颜色数量。

思路：

弦图与区间图-cdq：http://wenku.baidu.com/view/07f4be196c175f0e7cd13784.html

求出完美消除序列后，倒着贪心染色肯定是最优的

代码：

#include <bits/stdc++.h>#define F(x) (x + n + 1)const int Maxn = 10005;const int Maxm = 1000050;using namespace std;namespace IO { inline char get(void) { static char buf[1000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(int &x) { x = 0; static char c; for (; !(c >= '0' && c <= '9'); c = get()); for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); }};int n, m;int head[Maxn << 1], sub;struct Edge { int to, nxt; Edge(void) {} Edge(const int &to, const int &nxt) : to(to), nxt(nxt) {}} edge[Maxm << 1];inline int add(int a, int b) { edge[++sub] = Edge(b, head[a]), head[a] = sub;}int best, f[Maxn], seq[Maxn];bool vis[Maxn];inline int Max(const int &a, const int &b) { return a > b ? a : b;}inline void MCS(void) { int V; for (int i = n; i; i--) { V = 0; for (int j = 1; j <= n; j++) if (!vis[j] && f[j] >= f[V]) V = j; vis[V] = 1; seq[i] = V; for (int j = head[V], v; j; j = edge[j].nxt) { v = edge[j].to; f[v]++; } }}int xx[Maxn];inline void color(int u) { for (int i = head[u], v; i; i = edge[i].nxt) { v = edge[i].to; if (f[v] == -1) continue; xx[f[v]] = u; } for (int i = 1; f[u] == -1; i++) if (xx[i] != u) f[u] = i;}int main(void) { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); IO::read(n), IO::read(m); for (int i = 1; i <= m; i++) { int a, b; IO::read(a), IO::read(b); add(a, b), add(b, a); } MCS(); memset(f, -1, sizeof f); memset(xx, -1, sizeof xx); for (int i = n; i; i--) color(seq[i]); int ans = 0; for (int i = 1; i <= n; i++) ans = Max(ans, f[i]); cout << ans << endl; return 0;}

完。

By g1n0st

上一篇：hdu1010：Tempter of the Bone

下一篇：Struts的路径匹配原则（访问路径）