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

# 动态规划？~~（我不会）~~ ### 直接找规律搜索!!! ------------ # 题外话: 可能本人的思路跟楼下们相同，反正我看不懂$qwq$（本人很菜） 所以我就自己琢磨，然后希望能表述清楚，我做完后偷瞄了楼下$dalao$们的代码，好像差不多$qwq$~~（尴尬）~~ ------------ # 思路： 这道题目不难，我也不知道怎么用$dp$做$qwq$ ### 先说做法（至于为什么下文会提到）： 我们搜索每一个没访问过的点，对于搜索进来的这条边，我们不管它，让它继续搜索下去，直到访问了每个节点后，统计度数，如果现在是偶数度的话，我们就连上最开始搜索进来的边，保证当前点是奇数度 ### 知道你们现在还迷糊$qwq$，来人啊，上性质!!! 于是我门开始找性质： $1$、只需要一条边的变化，就能从奇数度与偶数度相互转换（废话） 也就是说一个点如果多一条边或者少一条边，就能从奇数度变为偶数度，或者从偶数度变为奇数度（感觉我在侮辱你们智商） ### 那么，来人啊!上样例!!! $\quad1-2$ $\,\,\quad$\$\quad $/ $\quad\quad3-4$ 我们从$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$ $\quad1-2$ $\,\,\quad$\$\quad $/ $\quad\quad3-4$ 我们还是从$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$啦 **记得连边连双向边** #### 最后到了美滋滋的代码时间~~~ ~~~cpp #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]); } ~~~