UVAOJ208 | 哈喽哈咯

Written by razrlele 16:14 March 15, 2015

UVAOJ208

这题隐藏的真深啊，看起来这么单纯可爱的一道DFS我居然TLE了两次。。。

我果然还是太naive了。。。

总而言之，虽然数据范围很小，但是依旧需要剪枝，在DFS之前首先要预处理一下，排除掉无法抵达终点的点，只用从终点开始反过来DFS遍历即可。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

/********************************************************

* File Name: uvaoj208.cpp

* Author: razrLeLe

* Mail: razrlele@gmail.com

* Homepage: https://yueyu.io

* Created Time: Sun 15 Mar 2015 02:19:46 PM CST

******************************************************/

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#include "list"

#include "stack"

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

const int MAXN = 25;

int G[MAXN][MAXN];

int numcase, end, ans;

bool vis[MAXN];

bool ok[MAXN];

int array[MAXN];

int dealArray[MAXN];

int largestNum;

void solve(int u, int len)

{

if(u == end)

{

ans++;

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

{

printf("%d", array[i]);

if(i == len-1)

printf("\n");

else

printf(" ");

}

return ;

}

for(int i = 1; i <= largestNum; i++ )

{

if(ok[i])

if(!vis[i] && G[u][i])

{

vis[i] = true;

array[len] = i;

solve(i, len+1);

vis[i] = false;

}

return ;

}

void preDeal(int u, int len)

{

if(u == 1)

{

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

ok[dealArray[i]] = true;

return ;

}

for(int i = 1; i <= largestNum; i++)

{

if(G[u][i] && !vis[i])

{

vis[i] = true;

dealArray[len] = i;

preDeal(i, len+1);

vis[i] = false;

}

return ;

}

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

numcase = 0;

while(~scanf("%d", &end))

{

printf("CASE %d:\n", ++numcase);

int x1, x2;

memset(G, 0, sizeof(G));

memset(vis, false, sizeof(vis));

memset(ok, false, sizeof(ok));

largestNum = 0;

while(scanf("%d %d", &x1, &x2) && (x1 || x2))

{

G[x1][x2] = 1;

G[x2][x1] = 1;

largestNum = max(largestNum, max(x1, x2));

}

array[0] = 1;

ans = 0;

ok[end] = true;

dealArray[0] = end;

preDeal(end, 1);

memset(vis, false, sizeof(vis));

vis[1] = true;

solve(1, 1);

printf("There are %d routes from the firestation to streetcorner %d.\n", ans, end);

}

return 0;

}