Codeforces 1186F - Vus the Cossack and a Graph 模拟乱搞/欧拉回路

题意：给你一张无向图，要求对这张图进行删边操作，要求删边之后的图的总边数 >= ceil((n + m) / 2), 每个点的度数 >= ceil(deg[i] / 2)。（deg[i]是原图中i的度数）

思路1：模拟 + 乱搞

直接暴力删就行了，读入边之后随机打乱一下就很难被hack了。

代码：

#include <bits/stdc++.h>

#define LL long long

#define INF 0x3f3f3f3f

#define db double

#define pii pair<int, int>

using namespace std;

const int maxn = 1000010;

struct node {

	int u, v, id;

};

vector<node> G;

int deg[maxn], limit[maxn], a[maxn];

pii b[maxn];

const LL mod = 1e9 + 7;

LL add(LL x, LL y) {return (x + y) % mod;}

LL mul(LL x, LL y) {return (x * y) % mod;}

bool vis[maxn];

bool cmp(int x, int y) {

	return deg[x] > deg[y];

}

int main() {

	int n, m, u, v;

	scanf("%d%d", &n, &m);

	int tot_limit = (n + m + 1) / 2;

	for (int i = 1; i <= m; i++) {

		scanf("%d%d", &u, &v);

//		G[u].push_back((node){u, v, i});

//		G[v].push_back((node){v, u, i});

		G.push_back((node){u, v, i});

		deg[u]++;

		deg[v]++;

	}

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

		limit[i] = (deg[i] + 1) / 2;

	}

	random_shuffle(G.begin(), G.end());

	int ans = m;

	for (int j = 0; j < G.size() && ans > tot_limit; j++) {

		int v = G[j].v, now = G[j].u;

		if(deg[v] == limit[v]) continue;

		if(deg[now] == limit[now]) continue;

		vis[j] = 1;

		ans--;

		deg[v]--;

		deg[now]--;

	}

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

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

		if(vis[i]) continue;

		printf("%d %d\n", G[i].u, G[i].v);

	}

}

思路2（官方题解）：新建0号点，把0号点和图中所有度数为奇数的点相连，形成一张新图。在新图上跑一遍欧拉回路，把欧拉回路记录的边中偶数位置的删掉，删的时候如果是新加的边，就直接删了。否则，看一下这条边相邻的两条边是不是新加的边并且可以删，如果可以，那就删新加的边，否则删这条边。即迫不得已的情况才会删除原图的边。

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000010;

struct edge {

	int u, v, flag;

};

int st[maxn * 2], ans[maxn * 2], re[maxn * 2];

edge a[maxn * 2];

int head[maxn], id[maxn * 4], Next[maxn * 4], ver[maxn * 4], tot, totm, tot_ans;

bool v[maxn * 4], vis[maxn * 4];

int deg[maxn];

int Top;

void add(int x, int y, int z) {

	ver[++tot] = y, id[tot] = z, Next[tot] = head[x], head[x] = tot;

}

void euler (int s) {

	tot_ans = 0;

	st[++Top] = s;

	while(Top > 0) {

		int x = st[Top], i = head[x];

		while(i && v[i]) i = Next[i];

		if(i) {

			st[++Top] = ver[i];

			re[Top] = id[i];

			v[i] = v[i ^ 1] = 1;

			head[x] = Next[i];

		} else {

			ans[++tot_ans] = re[Top];

			Top--;

		}

	}

}

int main() {

	int n, m, x, y;

	scanf("%d%d", &n, &m);

	tot = 1;

	for (int i = 1; i <= m; i++) {

		scanf("%d%d", &x, &y);

		totm++;

		a[totm] = (edge){x, y, 1};

		add(x, y, totm), add(y, x, totm);

		deg[x]++, deg[y]++;

	}

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

		if(deg[i] & 1) {

			totm++;

			a[totm] = (edge){0, i, 0};

			add(0, i, totm), add(i, 0, totm);

		}

	}

	int res = m;

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

		euler(i);

		for (int j = 2; j <= tot_ans; j += 2) {

			int now = ans[j];

			if(a[now].flag == 0) vis[now] = 1;

			else {

				int tmp = ans[j - 1];

				if(a[tmp].flag == 0 && vis[tmp] == 0) {

					vis[tmp] = 1;

					continue;

				}

				int Next = j + 1;

				if(j == tot_ans) Next = 1;

				tmp = ans[Next];

				if(a[tmp].flag == 0 && vis[tmp] == 0) {

					vis[tmp] = 1;

					continue;

				}

				vis[now] = 1;

				res--;

			}

		}

	}

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

	for (int i = 1; i <= totm; i++) {

		if(vis[i] == 0) {

			if(a[i].flag == 1) {

				printf("%d %d\n", a[i].u, a[i].v);

			}

		}

	}

}

//6 6

//3 4

//4 5

//5 3

//1 3

//1 2

//2 3

巴特西

Codeforces 1186F - Vus the Cossack and a Graph 模拟乱搞/欧拉回路

最新文章

热门文章