题解 P3022 【[USACO11OPEN]奇数度Odd degrees】

3493441984zz · 2019-02-02 10:53:09 · 题解

动态规划？（我不会）

直接找规律搜索!!!

题外话:

可能本人的思路跟楼下们相同，反正我看不懂qwq（本人很菜）

所以我就自己琢磨，然后希望能表述清楚，我做完后偷瞄了楼下dalao们的代码，好像差不多qwq（尴尬）

思路：

这道题目不难，我也不知道怎么用dp做qwq

先说做法（至于为什么下文会提到）：

我们搜索每一个没访问过的点，对于搜索进来的这条边，我们不管它，让它继续搜索下去，直到访问了每个节点后，统计度数，如果现在是偶数度的话，我们就连上最开始搜索进来的边，保证当前点是奇数度

知道你们现在还迷糊qwq，来人啊，上性质!!!

于是我门开始找性质：

我们从1号出发，搜索到2节点，继续搜索到3号节点，3号节点不能去1号，因为1被访问过了，所以到4去，而4号节点没有能走的地方了，于是我们统计4号点的度数为0（不算3-4这条搜索进来的边），那么现在4号节点就是偶数度，那么我们只能通过连上搜索进来的这条边3-4来保证4号点是奇数度

于是保留3-4这条边，那么返回到3节点，3节点相邻的1,2,4都被访问过了，于是统计度数，因为不算2-3这条边，所以3的度数为1，因为与4连了一条边，而现在是奇数度，所以我们不能连上2-3这条边，不然就多此一举的从奇数度变为了偶数度

那么又返回到2节点，与之相邻的点也都被访问过了，那么统计度数，由于1-2这条搜索进来的边先不管，而2-3这条边不连，所以2号点的度数为0，那么我们就必须连上1-2这条搜索进来的边来保证当前点是奇数度

于是保留1-2这条边，返回到1节点，发现没有与之相邻没访问过的点了，那么统计度数为1，因为与2连了边，那么也就方案成立了，所有点的度数都是奇数度啦

所以我们就连了1-2,3-4保证所有点是奇数度

等等？？样例输出不是这样啊？？

不是有苏卿念dalao提供的SPJ嘛

那么样例输出是怎么来的呢？？

其实是访问的顺序不一样导致的，那就再模拟一遍吧qwq

我们还是从1号点开始搜索，这次我们不先去2号点，而是去3号点，那么到了3号点后，我们随便往哪走，就先往2走吧，到了2号点后，发现不能走了，并且度数为0，那么就必须连上3-2这条边，返回到3节点，搜索到4号点，发现不能走了，于是统计度数为0，于是必须连上3-4这条边，返回到3节点后，发现不能走了，统计度数为2，那么就必须连上1-3，保证当前点是奇数度，那么返回到1节点，统计度数为1，于是完美结束

那么保留的边就是1-3,2-3,3-4啦

记得连边连双向边

最后到了美滋滋的代码时间~~~

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 50007
#define M 100007
using namespace std;
struct Edge
{
    int to,nxt,id;
}edge[M<<1];
int n,m,cnt;
int head[N],ans[M];
bool vis[N];
void Add(int u,int v,int id)
{
    edge[++cnt]=(Edge){v,head[u],id};
    head[u]=cnt;
}
bool Dfs(int u)
{
    vis[u]=1;
    int du=0;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(vis[v])
            continue;
        if(Dfs(v))
        {
            ++du;
            ans[++cnt]=edge[i].id;
        }
    }
    if(du%2==0)
        return 1;
    else
        return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        Add(u,v,i);
        Add(v,u,i);
    }
    cnt=0;
    for(int i=1;i<=n;++i)
        if(!vis[i])
            if(Dfs(i))
            {
                printf("-1");
                return 0;
            }
    sort(ans+1,ans+1+cnt);
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;++i)
        printf("%d\n",ans[i]);
}