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 }