GDKOI 2021 提高組 Day1 第一題 割（貪心+二分圖染色）

GDKOI 2021 提高組 Day1 第一題 割

題目大意

• 給出一種方案使 n n n個點 m m m條邊分成兩部分，兩部分之間的邊數 ≥ m 2 \ge\frac{m}{2} ≥2m​。
• n ≤ 1 0 5 , m ≤ 2 ∗ 1 0 5 n\le10^5,m\le2*10^5 n≤105,m≤2∗105

題解

• 沒用的邊删去後，剩下的部分是一張二分圖，考慮貪心染色。
• DFS的過程中，每到一個未染色的點，統計與它相鄰的點的顔色，将它自己染為較少的那種，令這些點有 s s s個，即邊共 s s s條，這樣可以保證連出的邊 ≥ s 2 \ge\frac{s}{2} ≥2s​，那麼最後連出的邊 ≥ m 2 \ge\frac{m}{2} ≥2m​。

代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
#define M 200010
int last[N], nxt[M * 2], to[M * 2], len = 1;
int co[N], sum = 0;
void add(int x, int y) {
	to[++len] = y;
	nxt[len] = last[x];
	last[x] = len;
}
void dfs(int k) {
	int s0 = 0, s1 = 0;
	for(int i = last[k]; i; i = nxt[i]) {
		s0 += (co[to[i]] == 0), s1 += (co[to[i]] == 1);
	}
	co[k] = (s1 <= s0);
	sum += min(s1, s0);
	for(int i = last[k]; i; i = nxt[i]) if(co[to[i]] == -1) dfs(to[i]);
}
int main() {
	int n, m, i, x, y;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		add(x, y), add(y, x);
	}
	memset(co, 255, sizeof(co));
	for(i = 1; i <= n; i++) if(co[i] == -1) dfs(i);
	for(i = 1; i <= n; i++) printf("%d ", co[i]);
	return 0;
}
           

自我小結

• 其實這題在寫的時候本意是貪心騙分，但在寫的過程中發下這種做法正确性是保證的。