UVA208（Firetruck）

//终于有一天，Leosu想起了自己的简书密码。。
题目就不复制了，附上题目连接：https://vjudge.net/problem/UVA-208
这道题对于学过经典暴搜算法DFS和BFS的同学来讲思路非常简单，也非常好写，思路就是DFS暴力搜索不过考虑到字典序问题所以可以提前排序。于是我们就写出了这样的代码：提交上去却显示TLE。。

import java.util.*;
import java.math.*;
import java.lang.*;
public class Main{
    public static int [][]firestreet = new int[30][30];
    public static int []way = new int[30];
    public static boolean []visit = new boolean[30];
    public static int cnt;
    public static void DFS(int cur,int root,int n){
        if(cur==n){
            System.out.print("1 ");
            for(int i = 0;i<root;i++){
                System.out.print(way[i]+" ");
            }
            System.out.println();
            cnt++;
            return;
        }
        for(int i = 1;i<=firestreet[cur][0];i++){
            if(!visit[firestreet[cur][i]]){
                visit[firestreet[cur][i]] = true;
                way[root] = firestreet[cur][i];
                DFS(firestreet[cur][i],root+1,n);
                visit[firestreet[cur][i]] = false;
            }
        }
        return;
    }
    public static void main(String[]args){
        Scanner cin = new Scanner(System.in);
        int t = 1;
    while(cin.hasNext()){
        int streetcorner = cin.nextInt();
        Arrays.fill(visit,false);
        for(int i = 1;i<=21;i++)
            Arrays.fill(firestreet[i],0);
        while(true){
            int x = cin.nextInt(),y = cin.nextInt();
            if(x==0&&y==0) break;
            firestreet[x][0]++;
            firestreet[y][0]++;
            firestreet[x][firestreet[x][0]] = y;
            firestreet[y][firestreet[y][0]] = x;
        }
        for(int i = 1;i<=21;i++){
            Arrays.sort(firestreet[i],1,firestreet[i][0]+1);
        }
        cnt = 0;
        visit[1] = true;
        DFS(1,0,streetcorner);
        System.out.printf("CASE %d:",t++);
        System.out.println();
        System.out.printf("There are %d routes from the firestation to streetcorner %d.",cnt,streetcorner);
        System.out.println();
    }
    }
}

一开始我以为是JAVA读写太慢于是改成快读快输疯狂提交，结果却是疯狂TLE。。直到后来我用c++写交也显示TLE的时候我意识到是一开始的思路就有问题，后来看了网上的做法，这道题虽然只有21个消防站但数据会给出无法到达终点站但路径却十分曲折的情况，所以才会出现TLE，所以有一个做法就是先用并查集看1是否可以到终点站再来觉得是否DFS，我改动了一下之前的代码，AC了，代码如下：
JAVA版本（采用了快读，用scanner应该也能AC）：

import java.util.*;
import java.math.*;
import java.lang.*;
import java.io.*;
public class Main{
    public static int [][]firestreet = new int[30][30];
    public static int []way = new int[30];
    public static boolean []visit = new boolean[30];
    public static int []father = new int[30];
    public static int cnt;
    public static int myfind(int x){
        int r = x;
        while(father[r]!=r)
            r = father[r];
        int i = x,j;
        while(i!=r){
            j = father[i];
            father[i] = r;
            i = j;
        }
        return r;
    }
    public static void DFS(int cur,int root,int n){
        if(cur==n){
            System.out.print("1 ");
            for(int i = 0;i<root;i++){
                if(i!=root-1)
                    System.out.print(way[i]+" ");
                else
                    System.out.print(way[i]);
            }
            System.out.println();
            cnt++;
            return;
        }
        for(int i = 1;i<=firestreet[cur][0];i++){
            if(!visit[firestreet[cur][i]]){
                visit[firestreet[cur][i]] = true;
                way[root] = firestreet[cur][i];
                DFS(firestreet[cur][i],root+1,n);
                visit[firestreet[cur][i]] = false;
            }
        }
        return;
    }
    public static void main(String[]args)throws IOException{
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        //PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int t = 1;
    while(in.nextToken() != StreamTokenizer.TT_EOF){
        int streetcorner;
        streetcorner = (int) in.nval;
        for(int i = 0;i<=21;i++){
            father[i] = i;
        }
        for(int i = 1;i<=21;i++)
            Arrays.fill(firestreet[i],0);
        Arrays.fill(visit,false);
        while(true){
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int y = (int) in.nval;
            if(x==0&&y==0) break;
            father[myfind(x)] = myfind(y);
            firestreet[x][0]++;
            firestreet[y][0]++;
            firestreet[x][firestreet[x][0]] = y;
            firestreet[y][firestreet[y][0]] = x;
        }
        cnt = 0;
        System.out.printf("CASE %d:",t++);
        System.out.println();
        if(myfind(1)==myfind(streetcorner)){
            for(int i = 1;i<=21;i++){
                Arrays.sort(firestreet[i],1,firestreet[i][0]+1);
            }
            visit[1] = true;
            DFS(1,0,streetcorner);
        }
        System.out.printf("There are %d routes from the firestation to streetcorner %d.",cnt,streetcorner);
        System.out.println();
    }
    }
}

C++11版本

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int firestreet[30][30],way[30],pre[30],cnt;
bool visit[30];
int myfind(int x){
    int r = x;
    while(pre[r]!=r)
        r = pre[r];
    int i = x,j;
    while(i!=r){
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void DFS(int cur,int root,int n){
    if(cur==n){
            printf("1 ");
            for(int i = 0;i<root;i++){
                if(i!=root-1)
                    printf("%d ",way[i]);
                else
                    printf("%d",way[i]);
            }
            printf("\n");
            cnt++;
            return;
        }
        for(int i = 1;i<=firestreet[cur][0];i++){
            if(!visit[firestreet[cur][i]]){
                visit[firestreet[cur][i]] = true;
                way[root] = firestreet[cur][i];
                DFS(firestreet[cur][i],root+1,n);
                visit[firestreet[cur][i]] = false;
            }
        }
        return;
}
int main()
{
    //freopen("text.txt","r",stdin);
    int t = 1,streetcorner;
    while(cin>>streetcorner){
        memset(firestreet,0,sizeof(firestreet));
        memset(visit,false,sizeof(visit));
        for(int i = 0;i<=21;i++){
            pre[i] = i;
        }
        while(true){
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==0||y==0) break;
            pre[myfind(x)] = myfind(y);
            firestreet[x][0]++;
            firestreet[y][0]++;
            firestreet[x][firestreet[x][0]] = y;
            firestreet[y][firestreet[y][0]] = x;
        }
        cnt = 0;
        printf("CASE %d:\n",t++);
        if(myfind(1)==myfind(streetcorner)){
            for(int i = 1;i<=21;i++){
                if(firestreet[i][0]!=0){
                    sort(firestreet[i]+1,firestreet[i]+firestreet[i][0]+1);
                }
            }
            visit[1] = true;
            DFS(1,0,streetcorner);
        }
        printf("There are %d routes from the firestation to streetcorner %d.\n",cnt,streetcorner);
    }
    return 0;
}

好了，现在我们再来回顾一下我们的做法：虽然AC了但也是因为数据给的太水，如果出现曲折并且1能到达6的情况同样可能WA，所以最好的办法是采用双向搜索加剪枝的做法。
//容我先休息一下再去写双向搜索加剪枝，写完回来更O(∩_∩)O~~

刚才看一下之前我的代码其实可以进一步优化就是用并查集查询下一节点是否与streetcorner相连，不是就舍去，这样的话就能大大的减少我们的搜索次数。//并查集+DFS还能这样用，学到了。。(^__) 嘻嘻……
附上优化代码：（其实就在DFS判断上多了一句话）

import java.util.*;
import java.math.*;
import java.lang.*;
import java.io.*;
public class UVA208{
    public static int [][]firestreet = new int[30][30];
    public static int []way = new int[30];
    public static boolean []visit = new boolean[30];
    public static int []father = new int[30];
    public static int cnt;
    public static int myfind(int x){
        int r = x;
        while(father[r]!=r)
            r = father[r];
        int i = x,j;
        while(i!=r){
            j = father[i];
            father[i] = r;
            i = j;
        }
        return r;
    }
    public static void DFS(int cur,int root,int n){
        if(cur==n){
            System.out.print("1 ");
            for(int i = 0;i<root;i++){
                if(i!=root-1)
                    System.out.print(way[i]+" ");
                else
                    System.out.print(way[i]);
            }
            System.out.println();
            cnt++;
            return;
        }
        for(int i = 1;i<=firestreet[cur][0];i++){
            if(!visit[firestreet[cur][i]]&&myfind(firestreet[cur][i])==myfind(n)){
                visit[firestreet[cur][i]] = true;
                way[root] = firestreet[cur][i];
                DFS(firestreet[cur][i],root+1,n);
                visit[firestreet[cur][i]] = false;
            }
        }
        return;
    }
    public static void main(String[]args)throws IOException{
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        //PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int t = 1;
    while(in.nextToken() != StreamTokenizer.TT_EOF){
        int streetcorner;
        streetcorner = (int) in.nval;
        for(int i = 0;i<=21;i++){
            father[i] = i;
        }
        for(int i = 1;i<=21;i++)
            Arrays.fill(firestreet[i],0);
        Arrays.fill(visit,false);
        while(true){
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int y = (int) in.nval;
            if(x==0&&y==0) break;
            father[myfind(x)] = myfind(y);
            firestreet[x][0]++;
            firestreet[y][0]++;
            firestreet[x][firestreet[x][0]] = y;
            firestreet[y][firestreet[y][0]] = x;
        }
        cnt = 0;
        System.out.printf("CASE %d:",t++);
        System.out.println();
        if(myfind(1)==myfind(streetcorner)){
            for(int i = 1;i<=21;i++){
                Arrays.sort(firestreet[i],1,firestreet[i][0]+1);
            }
            visit[1] = true;
            DFS(1,0,streetcorner);
        }
        System.out.printf("There are %d routes from the firestation to streetcorner %d.",cnt,streetcorner);
        System.out.println();
    }
    }
}