hdu 3018 Ant Trip 一笔画

缘起

日常浪费生命~ hdu 3018 Ant Trip

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
蚂蚁王国由N个点，M条边连接起来的无向图. 有一只蚂蚁想走遍王国. 每条边恰好走一次.
但是如果就靠它一只蚂蚁可能办不到. 所以它邀请了它的几位朋友, 每只蚂蚁从不同的点出发.
问最少需要几只蚂蚁?

【输入】
多样例. 每个样例开始于N和M，然后是M行，每行包含两个整数a和b(1<=a,b<=N,a!=b) 表示a和b之间有一条边,
一条路不会出现2次
N(1<=N<=100000),M(0<=M<=200000)

【输出】
每个样例输出最少几只蚂蚁

【样例输入】
3 3
1 2
2 3
1 3

4 2
1 2
3 4

【样例输出】
1
2

【限制】
1s

此题是水题~唯一需要知道的是一个连通无向图所需要的笔画数就是奇度点的个数除以2的商.但是题目没说此无向图连通,所以先用并查集分块,然后每个块的笔画数之和就是答案了

说实话, 我不太明白为什么孤立点不能算连通分支去?（我没理解题意? 恳请高手解读题意~） 反正要加这个限制, 不然就wa（到吐）. 不管了，反正主要思想明白就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

int n,m,f[100005],deg[100005],sum[100005];

int getf(int i)
{
	return f[i]<0?i:f[i]=getf(f[i]);
}

void merge(int i, int j)
{
	int fi = getf(i), fj = getf(j);
	if (fi==fj)
	{
		return;
	}
	if (f[fi]<f[fj])
	{
		f[fi] += f[fj];
		f[fj] = fi;
	}
	else
	{
		f[fj] += f[fi];
		f[fi] = fj;
	}
}

int main()
{	
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%d%d",&n,&m))
	{
		memset(f, -1, sizeof(f));
		memset(deg, 0, sizeof(deg));
		memset(sum, 0, sizeof(sum));
		while(m--)
		{
			int a,b;
			scanf("%d%d", &a,&b);
			deg[a]++, deg[b]++;
			merge(a,b);
		}
		for (int i = 1,fi; i<=n; i++)
		{
			if (deg[i]&1) // 如果是奇度点
			{
				fi = getf(i); // 找到它所在的连通分支
				if (~f[fi]) // 如果不是孤立点
				{
					sum[fi]++;
				}
			}
		} // sum[i]记录了i是它的连通分支的并查集老大,并且这个连通分支的奇度点的个数
		int ans = 0;
		for (int i = 1; i<=n; i++)
		{
			if (f[i]<0 && ~f[i])  // 如果是并查集老大,并且不是孤立点
			{
				if (!sum[i]) // 该连通分支存在欧拉回路,可以一笔画
				{
					ans++;
				}
				else
				{
					ans+=(sum[i]>>1); // 否则就是奇度点个数/2
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 93ms
Memory 2384kB
Length 1103
Lang G++
Submitted 2019-09-07 09:32:17
Shared
RemoteRunId 30523325