CodeForces - 789D Weird journey(詳細講解,其實很簡單)

這題一開始看到是懵逼的,百度了很多題解也是懵逼的,以為是一個很難得圖論問題,因為我圖論也隻會一些模版.但是後來仔細看發現其實這題不需要什麼圖的基礎,也是一個思維題.

題目描述,需要這樣一種路線,但是他區分不同的路線,是根據那些路走了兩遍,那些路走了一遍來的,而不是行走順序,這一點首先要看清楚.

第二呢,注意到這種路線滿足所有點都被經過的特點,是以這是歐拉通路的定義,如果不知道可以百度,很簡單的.

是以現在就是一個計數問題,找到所有将m-2條邊複制一次,使得圖滿足歐拉通路定義即可.

不複制的兩條邊分三種情況.

1.都是自環,顯然可以,為C(loop,2).

2.一自環一非自環,為loop*(m-loop).

3.兩個非自環,注意需要滿足他們接在同一個點上,是以為

for(所有點)

ans+=C(非自環邊數,2).

/*  xzppp  */
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <list>
using namespace std;
#define FFF freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mp make_pair
typedef long long  LL;
typedef unsigned long long ULL;
const int MAXN = ;
const LL  INF = ;
const int MOD = +;
int vis[MAXN+],self[MAXN+];
vector<int> G[MAXN+];
void dfs(int x)
{
    for (int i = ; i < G[x].size(); ++i)
        if(vis[G[x][i]]==)
        {
            vis[G[x][i]]=;
            dfs(G[x][i]);
        }
}
int main()
{
    //FFF
    LL n,m,loop=,cnt=;
    cin>>n>>m;
    for (int i = ; i < m; ++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        u--;
        v--;
        if(u==v)
        {
            loop++;
            self[u] = ;
        }
        else
        {   
            G[u].push_back(v);
            G[v].push_back(u);
        }
        vis[v]=vis[u]=;
    }
    bool can = true;
    for (int i = ; i < n; ++i)
    {
        if(vis[i]==)
        {
            dfs(i);
            if(++cnt>)
            {
                can = false;
                break;
            }
        }
    }
    LL ans = ;
    if(can)
    {
        for(int i=;i<n;++i)
        {
            int num = G[i].size();
            ans+=(L*num*(num-))/;
        }
    }
    ans += (L*(loop-)*loop)/;
    ans += L*loop*(m-loop);
    if(can)
        cout<<ans<<endl;
    else
        cout<<"0"<<endl;
    return ;
}