CodeForces 788B - Weird journey [ 分类讨论 ] [ 欧拉通路 ]

题意：

给出无向图.

good way : 仅有两条边只经过一次，余下边全经过两次的路

问你共有多少条不同的good way。

两条good way不同仅当它们所经过的边的集合中至少有一条不同（很关键）

存在多个边连通分量的情况肯定是0.

当确定某两条边只经过一次的时候：

由于经过边的顺序不重要，余下边全经过两次，至多只有一条good way

那么把剩下经过两次的边拆分成两条经过一次的边，记现在的图是新图

原图中是否存在good way 就等价于新图中是否存在欧拉路

暴力枚举两条边判断肯定是要TLE的

那就要考虑怎样的两条边存在解

先不考虑自环：

当这两条边不相邻时：

由于只有这两条边的端点的度是奇数，其他点都是偶数，新图中共有四个点是奇数度，不存在欧拉路

当这两条边相邻时：

这两条边的三个端点中两个是奇数，余下都是偶数，存在欧拉回路

考虑自环

当其中有一条边是自环时：

自环只有一个端点，故自环的端点是偶数度，新图中只有两个奇数度点，存在欧拉回路

当两条边都是自环时：

所有点都是偶数度，存在欧拉回路

故存在解的情况：

两条边相邻 (去掉自环后的边):

枚举每个端点i, ans += Comb(edge[i].size(), 2);

其中一条边是自环:

ans += loopCnt * (m-1);

ans -= Comb(loopCnt, 2);//重复计算

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 const int MAXN = ;

 int n, m;

 vector<int> G[MAXN];

 int loop[MAXN], lcnt;

 int vis[MAXN];

 void dfs(int x)

 {

     if (vis[x]) return;

     vis[x] = ;

     for (int i = ; i < G[x].size(); i++)

         dfs(G[x][i]);

 }

 int main()

 {

     for (int i = ; i <= n; i++)

         G[i].clear(), vis[i] = loop[i] = ;

     lcnt = ;

     scanf("%d%d", &n, &m);

     int root;

     for (int i = ; i <= m; i++)

     {

         int x, y; scanf("%d%d", &x, &y);

         if (x == y) loop[x]++ ,lcnt++;

         else

         {

             G[x].push_back(y);

             G[y].push_back(x);

         }

         root = x;

     }

     dfs(root);

     bool flag = ;

     for (int i = ; i <= n; i++)

     {

         if (!vis[i] && (G[i].size() || loop[i]))

             flag = ;

     }

     if (!flag)

     {

         puts(""); return ;

     }

     LL ans = ;

     for (int i = ; i <= n; i++)

     {

         int sz = G[i].size();

         ans += (LL)sz*(sz-) / ;

     }

     ans += (LL)lcnt * (m-);

     ans -= (LL)lcnt * (lcnt-) / ;

     printf("%lld\n", ans);

 }

巴特西

CodeForces 788B - Weird journey [ 分类讨论 ] [ 欧拉通路 ]

最新文章

热门文章