https://www.luogu.org/problemnew/show/CF788B从国家集训队的论文集里看到的题,既然没人写题解那我也就参考一下论文集里的话写一篇题解了。
这里把陈通写的论文放上来供大家看一下吧。
解法
题意转化一下就是说让原图 的每条边建两遍,那么显然是一张欧拉回路。要求删去两条边之后这张图存在欧拉路径。
既然存在欧拉路径,那么必然存在两个或者零个奇度点。删去一条边会使得两个端点的度数减一,那么只存在以下三种合法的删边方式。
1.删除两条自环(删除后为欧拉图)。
2.删除两条有公共点的边(删除后为半欧拉图)。
3.删除一条自环与一条边(删除后为半欧拉图)。
那么分别统计方案就可以了。
注意这张图不一定连通,可能存在无解的方案。需要想办法判断每条边是不是都走过了,我的代码里是是用 判断了一下边的度数。
Source Code
#include <cstdio> #include <cstring> #include <iostream> #include <set> const int MAXN = 1e6 + 7; int f[MAXN], h[MAXN], self[MAXN]; int deg[MAXN], my, es; int tot, t2; struct Edge { int t, next; } edge[MAXN << 1]; int head[MAXN], cnt; bool vis[MAXN]; long long ans; void add(int u, int v) { edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt; } void dfs(int u) { tot += deg[u]; t2 += self[u]; vis[u] = true; ans += (1LL * deg[u] * (deg[u] - 1LL) / 2LL); for (int e = head[u]; e; e = edge[e].next) { int v = edge[e].t; if (!vis[v]) dfs(v); } } int main(int argc, char *argv[]) { int n, m, r; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); if (u == v) my++, self[u]++; else deg[u]++, deg[v]++, es++, add(u, v), add(v, u); } ans = 1LL * es * my + 1LL * (1LL * my * (my - 1)) / 2; for (int i = 1; i <= n; i++) { if (!vis[i] && deg[i]) {dfs(i); break;} } if (tot != es * 2) ans = 0; if (t2 != my) ans = 0; printf("%lld\n", tot == es * 2 ? ans : 0); return 0; }