图论训练之十二

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]);
}

图论训练之十二

原文：https://www.cnblogs.com/wzxbeliever/p/11731276.html