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]);
- }
来源: http://www.bubuko.com/infodetail-3255081.html