https://www.luogu.org/problem/P3022
吐槽:什么狗屁标签,动态规划?单调队列?
还有就是我为什么纯dfs的题总是做不到
分析:这道题有special judge说明乱搞能过
结论:
直接在原图的每一个连通块的一颗树上进行树形dp
考虑u-v这条边
如果与v相连的树边为偶数,则u-v这条边保留
如果为奇数,则u-v这条边不保留
如果成立的话,则整个图一定是成立的,反之整个图也不成立
至于为什么这么干
找了很多的题解,都没说个东西,然后我想了一晚上一上午也没肝出来
无奈我也就只能这样谢了,见谅
乱搞code:
#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]);
}