6-14 Inspector s Dilemma uva12118（欧拉道路）

　　题意：给出一个国家城市个数n 所需走过道路个数e 每条道路长t 该国家任意两个城市之间都存在唯一道路长t 要求：找一条最短的路遍历所有所需走过的路

一开始以为是图的匹配但是好像又无从下手

参考了其他人的做法发现要用欧拉道路的知识

欧拉道路：如果一个联通图，形成欧拉路，那么度数为奇数的有两个，如果是欧拉环，则全部为度数为偶数的顶点。

一个图的度数为奇数的个数一定是偶数！！！！！

当一个联通块为一个环或者度数为奇数的个数恰巧为两个时不需要另外加路了一笔画就行

当一个联通块度数超过2时每两个奇数度的点可以用一条增加的路来连接就可以消去两个奇数度所以增广路=（奇数度点的个数-2）/2

还有就是两个不相连的联通块需要一条路连在一起用ans表示

#include<iostream>

#include<queue>

#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

#define N 1005

#define inf 0x3f3f3f3f

int du[N];

vector<int>g[N];

int vis[N];

int dfs(int x)

{

    int sum=;

    vis[x]=;

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

    {

        if(!vis[ g[x][i] ])

            sum+=dfs(g[x][i]);

    }

    if(du[x]%)

        return sum+;

    else

        return sum;

}

int main()

{

    int n,e,t;

    int ans;//联通块的个数

    int ans1;//奇数度要补的个数

    int cas=;

    while(scanf("%d%d%d",&n,&e,&t)==,n)

    {

        for(int i=;i<=n;i++)g[i].clear();

        memset(du,,sizeof du);

        memset(vis,,sizeof vis);

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

        {

            int a,b;

            scanf("%d%d",&a,&b);

            du[a]++;

            du[b]++;

            g[a].push_back(b);

            g[b].push_back(a);

        }

        ans=ans1=;

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

        {

            if(du[i]&&!vis[i])

            {

                ans++;

            int x=dfs(i);

            if(x>)

                ans1+=(x-)/;

            }

        }

        if(ans>)

            ans--;

        printf("Case %d: %d\n",++cas,t*( ans+ans1+e  ) );

    }

    return ;

}

巴特西

6-14 Inspector s Dilemma uva12118（欧拉道路）

最新文章

热门文章