Inspector's Dilemma（欧拉通路）

In a country, there are a number of cities. Each pair of city is connected by a highway, bi-directional of course. A road-inspector’s task is to travel through the highways (in either direction) and to check if everything is in order. Now, a road-inspector has a list of highways he must inspect. However, it might not be possible for him to travel through all the highways on his list without using other highways. He needs a constant amount of time to traverse any single highway. As you can understand, the inspector is a busy fellow does not want to waste his precious time. He needs to know the minimum possible time to complete his task. He has the liberty to start from and end with any city he likes. Please help him out.

Input

The input file has several test cases. First line of each case has three integers: V (1 ≤ V ≤ 1000), the number of cities, E (0 ≤ E ≤ V ∗ (V − 1)/2), the number of highways the inspector needs to check and T (1 ≤ T ≤ 10), time needed to pass a single highway. Each of the next E lines contains two integers a and b (1 ≤ a, b ≤ V , a ̸= b) meaning the inspector has to check the highway between cities a and b. The input is terminated by a case with V = E = T = 0. This case should not be processed.

Output

For each test case, print the serial of output followed by the minimum possible time the inspector needs to inspect all the highways on his list. Look at the output for sample input for details.

这道题需要先理解一个概念：欧拉通路，要想达到题目说的那样每个边恰好只走一次，除了起点和终点外，其他点都不能是奇度点。

那么就这么做，首先每次都寻求一块的连通块，统计它们的奇数点个数，然后每个两个奇数点都至少需要一条边来使他变成偶数点，然后又因为起点和终点可以为奇数点，这种情况从中剪去。

DFS找奇数点+欧拉方法解决。

#include"iostream"

#include"cstring"

#include"vector"

using namespace std;

const int maxn=400000;

 vector<int>q[1010];

int cnt;

int book[1010];

void DFS(int n)

{

    if(book[n]!=0)

        return;

    book[n]=1;

    cnt+=q[n].size()&1;

    for(int k=0;k<q[n].size();k++)

        DFS(q[n][k]);

    return;

}

int main()

{

    int v,e,c,flag,f=1,a,b;

    while(cin>>v>>e>>c&&v)

    {

     memset(book,0,sizeof(book));

     for(int k=0;k<1010;k++)

        q[k].clear();                //每次都必须删除上次残余数据

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

    {

      cin>>a>>b;

      q[a].push_back(b);

      q[b].push_back(a);

    }

    int ans=0;

    cnt=0;

    for(int j=1;j<=v;j++)

    {

      //  cout<<book[j]<<' ';

        if(book[j]!=1&&!q[j].empty())

        {

        cnt=0;

        DFS(j);

        ans+=max(cnt,2);                  //每次的数都要大于二，以保证能够形成哈密顿图

        }

    }

    cout<<"Case "<<f++<<": "<<(max(ans/2-1,0)+e)*c<<endl;

    }

    return 0;

}

巴特西

Inspector's Dilemma（欧拉通路）

最新文章

热门文章