ZOJ 2103 Marco Popo the Traveler（dfs+欧拉路）

ゝ一纸荒年。 2022-06-11 00:47 100阅读 0赞

Marco Popo, the famous traveler, is traveling around the country of ACM. There are colored high-ways between cities (of course there is at most one high-way between any two cities), and his goal is to drive along each high-way once and only once. There is a strange rule to be followed when driving along: the color of one's tyres must match that of the high-way. As a result, he has to change tyres all the way he travels.  
  
Given the total number of cities and the high-way map, you should decide at least how many times Popo needs to change tyres. Notice that Popo only changes tyres in cities, and he is allowed to start and end with tyres of arbitrary color.

Input

There are several test cases. Each test case begins with a line containing the total number of cities N (0 < N <= 10), the total number of colors C (0 < C <= 6), and the total number of high-ways in the country H (0 < H <= 20). Then H lines follow, each has three integers a, b, and c (0 <= a, b < N, 0 <= c < C) separated with whitespaces. This denotes that there is a high-way between city a and city b with color c.

There is a single blank line between test cases. A test case with 0 terminates the input, and this test case is not to be processed.

Output

For each test case, print a line with the minimum number of times Popo has to change tyres, so that he can achieve his goal. Otherwise print a line containing "No" only.

Sample Input

4 3 5  
0 1 0  
1 2 1  
2 3 0  
3 0 1  
0 2 2

4 3 6  
0 1 0  
1 2 1  
2 3 0  
3 0 1  
0 2 2  
1 3 2

0 0 0

Sample Output

4  
No

题解：

比赛的时候没太看懂题目。。后来知道题目意思了发现是一题大水题。。题意就是有n个城市，c种颜色，h个高速公路，没经过一条路如果颜色不同就要换轮胎颜色，问你至少要用换几次轮胎。。看到数据那么小果断暴力dfs遍历，加上图论的一点知识就可以过，一次ac了

代码：

#include<iostream>
    #include<stdio.h>
    #include<map>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    #include<string>
    #include<cstring>
    using namespace std;
    const int INF=10086111;
    struct edge
    {
        int d1,d2;//记录该路通往的两个城市
        int col;//记录该路要用的颜色
    }a[25];
    int p[25][25];//记录每个城市可以通往的城市的路的标号
    int num[25];//记录每个城市连接的路
    int vis[25];//记录每条路是否被遍历
    int minn,n,m;
    void dfs(int index,int step,int s,int c)
    {
        if(step==m)//所有边遍历完了
        {
            if(minn>s)
                minn=s;
            return;
        }
        int i,j;
        for(i=0;i<num[index];i++)
        {
            if(!vis[p[index][i]])//遍历所有边
            {
                vis[p[index][i]]=1;//标记
                int t=a[p[index][i]].d1==index?a[p[index][i]].d2:a[p[index][i]].d1;//这一步判断是通往边的哪一个点
                if(!step)//如果是第一步就不计换胎数
                    dfs(t,step+1,s,a[p[index][i]].col);
                else
                {
                    if(c==a[p[index][i]].col)//颜色一样不计数
                        dfs(t,step+1,s,a[p[index][i]].col);
                    else
                        dfs(t,step+1,s+1,a[p[index][i]].col);
                }
                vis[p[index][i]]=0;//回溯
            }
        }
    }
    int main()
    {
        int i,j,s,x,y,z,d1;
        while(scanf("%d%d%d",&n,&s,&m)!=EOF)
        {
            if(!n&&!s&&!m)
                break;
            memset(num,0,sizeof(num));
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&x,&y,&z);
                a[i].d1=x;
                a[i].d2=y;
                a[i].col=z;
                p[x][num[x]]=i;
                p[y][num[y]]=i;
                num[x]++;
                num[y]++;//记录各种信息
            }
            int tot=0;
            for(i=0;i<n;i++)
            {
                if(num[i]%2)//记录奇数度数点的个数
                {
                    if(!tot)
                        d1=i;//顺便保存如果奇数点2个的情况的起始点
                    tot++;
                }
            }
            if(tot>2||tot==1)//不符合欧拉回路或通路的条件
            {
                printf("No\n");
                continue;
            }
            else
            {
                minn=INF;
                if(tot==0)
                {
                    for(i=0;i<n;i++)//遍历每一个节点开始的情况
                    {
                        memset(vis,0,sizeof(vis));//要初始化
                        dfs(i,0,0,0);
                        if(minn==INF)//说明有路不通
                            break;
                    }
                }
                else//奇数度数为两个要从d1开始搜
                {
                    memset(vis,0,sizeof(vis));
                    dfs(d1,0,0,0);
                }
            }
            if(minn==INF)//有路不通
            {
                printf("No\n");
            }
            else
                printf("%d\n",minn);
        }
        return 0;
    }