题解 洛谷P3022 [USACO11OPEN]奇数度Odd degrees

我感觉思路隔壁题解给的不够清楚啊……

感觉我无法直接理解隔壁dalao的“正经的图上神搜”啊……

那本蒟蒻就补充一下吧QwQ

这题的思路是这样的:

我们先不考虑断边,而是考虑连尽量多的边

继续考虑,对于每一个点,我们都考虑,对于它搜索过来的边(下文称其为“入边”),我们要不要连上,如果需要,那么我们的Dfs()Dfs()函数返回值为truetrue,否则为truetrue

再考虑入边之外的其他点。对于深搜搜到每一个点的时候,我们都考虑与它相邻且未被搜索的点,如果对于这些点,需要连上“入边”,我们就把当前搜索的这个点的度加上1

在搜索完与它相邻的点之后,我们看一看这个点的度,如果它已经是奇数度的话,我们就不需要连上它的入边了(returnreturn falsefalse),否则则需要连上入边,我们需要将当前这个点的入边加入答案,然后returnreturn truetrue

对于主函数,我们只需要将每个联通块都搜一遍即可QwQ,最后还有一点需要注意的,就是我们需要在搜索到每一个联通块的时候,如果发现一开始DfsDfs的返回值就是truetrue了,但是!这个点没有入边,所以就无解辣QwQ

最后放上与隔壁大佬超级像的代码

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
// Sooke bless me.
// LJC00118 bless me.
#include<bits/stdc++.h>

#define INF 2147483647
#define ll long long

int Inp(){
char c = getchar();
int Neg = 1;
while(c < '0' || c > '9'){
if(c == '-')
Neg = -1;
c = getchar();
}
int Sum = 0;
while(c >= '0' && c <= '9'){
Sum = ((Sum << 3) + (Sum << 1)) + c - '0';
c = getchar();
}
return Neg * Sum;
}

int Head[50010], Next[400010], End[400010];
bool Used[50010];
int Ans[50010], Index = 0;
int Cou = 0;

void Link(int a, int b){
Next[++Cou] = Head[a];
Head[a] = Cou;
End[Cou] = b;
}

bool Dfs(int Cur, int Edge){
Used[Cur] = true;
int Degree = 0;
for(int x = Head[Cur]; x != -1; x = Next[x]){
if(Used[End[x]])
continue;
if(Dfs(End[x], x))
Degree++;
}
if(Degree % 2 == 1)
return false;
Ans[++Index] = (Edge + 1) >> 1;
return true;
}

int main(){
memset(Head, -1, sizeof(Head));
int n = Inp();
int m = Inp();
for(int i = 1; i <= m; i++){
int a = Inp();
int b = Inp();
Link(a, b);
Link(b, a);
}
for(int i = 1; i <= n; i++)
if(!Used[i])
if(Dfs(i, -1)){
printf("-1");
return 0;
}
std::sort(Ans + 1, Ans + Index + 1);
printf("%d", Index);
for(int i = 1; i <= Index; i++)
printf("\n%d", Ans[i]);
}

QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动,使用 Azurus 作为主题。