BZOJ1006神奇的国度 弦圖染色 最大勢算法

@[弦圖染色, 最大勢算法]

Description

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA

相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2

...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,C

D,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，

最少可以分多少支队。

Input

第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋

友

Output

输出一个整数，最少可以分多少队

Sample Input

4 5

1 2

1 4

2 4

2 3

3 4

Sample Output

3

HINT

一种方案(1,3)(2)(4)

Solution

首先吐槽这道题的题意不清. 題目實際上要表達的意思是, 在一個無向弦圖中, 如何用最少個的顏色數量使得相邻两点的染色都不相同.

解決這個問題有一種簡單易行的辦法, 只能适用于弦图, 正確性無法證明, 但反正就是對的, 名字叫做最大勢算法.

然後再吐槽題目的數據, \({10}^{4}\)個點你確定真的可以跑的過去?

不管了, 反正就是A了. 鐵代碼:

#include<cstdio>

#include<cctype>

#include<cstring>

#include<climits>

#include<algorithm>

using namespace std;

inline int read()

{

	int x = 0, flag = 1;

	char c;

	while(! isdigit(c = getchar()))

		if(c == '-')

			flag *= - 1;

	while(isdigit(c))

		x = x * 10 + c - '0', c = getchar();

	return x * flag;

}

const int oo = INT_MAX;

const int N = 1 << 14, M = 1 << 20;

int top;

int head[N];

struct Edge

{

	int v, next;

}G[M << 1];

void add_edge(int u, int v)

{

	G[top].v = v, G[top].next = head[u], head[u] = top ++;

}

int w[N];

int rec[N];

int cmp(int x, int y)

{

	return w[x] > w[y];

}

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("BZOJ1006.in", "r", stdin);

	freopen("BZOJ1006.out", "w", stdout);

	#endif

	int n = read(), m = read();

	top = 0;

	memset(head, - 1, sizeof(head));

	for(int i = 0; i < m; i ++)

	{

		int u = read(), v = read();

		add_edge(u, v), add_edge(v, u);

	}

	memset(w, 0, sizeof(w));

	w[0] = - oo;

	memset(rec, 0, sizeof(rec));

	int ans = 0;

	for(int i = 0; i < n; i ++)

	{

		int u = 0;

		for(int i = 1; i <= n; i ++)

			if(w[i] > w[u])

				u = i;

		if(! rec[w[u]])

			ans ++, rec[w[u]] = 1;

		w[u] = - oo;

		for(int i = head[u]; i != - 1; i = G[i].next)

			w[G[i].v] ++;

	}

	printf("%d\n", ans);

}