题解 CF858F 【Wizard's Tour】

[也许更好的阅读体验cnblog](https://www.cnblogs.com/Morning-Glory/p/11437909.html) [也许更好的阅读体验csdn](https://blog.csdn.net/Morning_Glory_JR/article/details/100168725) # $\mathcal{Description}$ 给定一张 $n$ 个点 $m$ 条边的无向图，每条边连接两个顶点，保证无重边自环，不保证连通。 你想在这张图上进行若干次旅游，每次旅游可以任选一个点 $x$ 作为起点，再走到一个与 $x$ 直接有边相连的点 $y$，再走到一个与 $y$ 直接有边相连的点 $z$ 并结束本次旅游。 作为一个旅游爱好者，你不希望经过任意一条边超过一次，注意一条边不能即正向走一次又反向走一次，注意点可以经过多次，在满足此条件下，你希望进行尽可能多次的旅游，请计算出最多能进行的旅游次数并输出任意一种方案。 # $\mathcal{Solution}$ ## **20**分思路 先提供一个比较傻且只能得20分的思路 就是我们把每条边看做是一个点，距离为一的点之间连一条边 于是问题就变成了求最大匹配了 不过这样会把边的条数大大增大..... 妥妥的TLE ## **100**分思路 若仅是一棵树，那此题的做法还是很显然的 要保证边用的最多，按照树的深度从小到大考虑，即按照拓扑序将能匹配的匹配就是正确的 若不仅是一棵树，我们随便按照一种方式把它的生成树建出来 这样就有非树边和树边，对于每个点，我们先将其与父亲的边不考虑 设其周围有$n$条边 若$n$为偶数，就可以把它们两两搭配，有$\frac{n}{2}$种方法 若$n$为奇数，就拿一条边与其与父亲的边搭配，剩下的两两搭配 显然，这样做除了在根节点剩下一条边，其他的边都会被用到 # $\mathcal{Code}$ 实现部分说一下吧 我觉得我打得比其它人的简洁一些吧 大部分人用了一个$vector$去记录哪些边 实际上，我们可以直接把这些边匹配 用$f[x]$表示是否有一条与$x$相连且还没有匹配的边 每次拿到新边看看有没有为匹配的边，有的话它们就匹配 注意一条边只需考虑一次 ```cpp /******************************* Author:Morning_Glory LANG:C++ Created Time:2019年08月30日 星期五 09时08分56秒 *******************************/ #include <cstdio> #include <fstream> #include <cstring> using namespace std; const int maxn = 1000006; //{{{cin struct IO{ template<typename T> IO & operator>>(T&res){ res=0; bool flag=false; char ch; while((ch=getchar())>'9'||ch<'0') flag|=ch=='-'; while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar(); if (flag) res=~res+1; return *this; } }cin; //}}} int n,m,u,v,cnt,ans; int head[maxn],nxt[maxn],to[maxn];//edge int a[maxn],b[maxn],c[maxn],f[maxn];//ans bool vis[maxn]; //{{{add void add (int u,int v) { nxt[cnt]=head[u],head[u]=cnt,to[cnt++]=v; } //}}} //{{{dfs void dfs (int x) { vis[x]=true; for (int e=head[x];~e;e=nxt[e]){ int te=to[e]; to[e]=to[e^1]=0; if (te){ if (!vis[te]) dfs(te); if (f[te]) a[++ans]=x,b[ans]=te,c[ans]=f[te],f[te]=0; else if (f[x]) a[++ans]=f[x],b[ans]=x,c[ans]=te,f[x]=0; else f[x]=te; } } } //}}} int main() { memset(head,-1,sizeof(head)); cin>>n>>m; for (int i=1;i<=m;++i) cin>>u>>v,add(u,v),add(v,u); vis[0]=true; for (int i=1;i<=n;++i) if (!vis[i]) dfs(i); printf("%d\n",ans); for (int i=1;i<=ans;++i) printf("%d %d %d\n",a[i],b[i],c[i]); return 0; } ```