Codeforces Round #407 (Div. 2) D. Weird journey 思维+欧拉

时间:2021-12-27 06:21:55

D. Weird journey

链接:

http://codeforces.com/contest/789/problem/D

题意:

给你一个双向路径图(可能不连通且存在自环,同样的边不会出现两次),n个节点,m条边,要求划出一条路径,使得其中(m-2)条边每条边走两次,另外两条边每条边走一次,问有多少种不同的路径。

题解:

这题咋一看,像不像欧拉路,很像啊,欧拉路是划出一条路径经过所有的边一次且仅一次,而这个是选出(m-2)条边来走两次。那我们不妨将这(m-2)条边再建一条,比如,

u<-->v,那我们再建一条u<-->v。那么如果修改后的图能跑出一条欧拉路的话,那么就符合题意了,所以我们就枚举这些边。由于(m-2)可能比较大,那么我们就枚举这个2,即不增建的边。

我们判定欧拉路的依据是奇数度数节点只有两个或者没有。那么我们枚举每一条边,将此边不增,其他的每条边都扩增一条,那么此时除了这条边连接的两个端点(u!=v)

以外,其他的所有节点的度数都是偶数,这两个节点的度数都是奇数。等会,我们还差一条边,,,现在已经有两个节点度数是奇数了,那么我们要拆的下一条边就必须是与这两个节点相关的(可以自己想想为什么)那么这条边的贡献就是这两个节点所连得边的和-1了。还有就是如果你拆了某个自环的边,也是可以的。还有种情况就是你一开始选的是一个自环的边,那么你下一条要拆的随便那条边都行。

代码:

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define pb push_back
19 #define mp make_pair
20 #define all(x) (x).begin(),(x).end()
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll mod = 1e9 + 7;
26 const int inf = 0x3f3f3f3f;
27 const double eps = 1e-10;
28 const double pi = acos(-1.0);
29 // head
30 
31 const int MAX_N = 1e6 + 7;
32 struct Edge { int u, v; }e[MAX_N];
33 ll n, m;
34 VI G[MAX_N];
35 int vis[MAX_N];
36 int deg[MAX_N];
37 
38 void dfs(int v) {
39     vis[v] = 1;
40     rep(i, 0, G[v].size()) if (!vis[G[v][i]]) dfs(G[v][i]);
41 }
42 
43 int main() {
44     ios::sync_with_stdio(false);
45     cin >> n >> m;
46     int loop = 0;
47     rep(i, 0, m) {
48         int u, v;
49         cin >> u >> v;
50         e[i].u = u, e[i].v = v;
51         if (u != v) G[u].pb(v), G[v].pb(u);
52         else loop++;
53         deg[u]++, deg[v]++;
54     }
55     rep(i, 1, n + 1) if (deg[i]) { dfs(i); break; }
56     rep(i, 1, n + 1) if (!vis[i] && deg[i]) return puts("0"), 0;
57     ll ans = 0;
58     rep(i, 0, m) {
59         int x = e[i].u, y = e[i].v;
60         if (x != y) ans += G[x].size() - 1 + G[y].size() - 1 + loop;
61         else ans += m - 1;
62     }
63     cout << ans / 2 << endl;
64     return 0;
65 }