首页 > 代码库 > UVa208,Firetruck
UVa208,Firetruck
要事先判断结点1能否到达K,否则真的会超时的= =(我一开始不信,感觉应该能正常退出dfs啊,结果真的超时了)
我是判断的k是否与其他结点有路,是的话才dfs(数据水,居然过了)
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <queue>#define maxn 20+5using namespace std;struct Node{ int x,y;};int map[maxn][maxn],k,d[maxn],vis[maxn],tot,m;int init(){ memset(map,0,sizeof(map)); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); tot=0;m=0; int x,y; while(cin>>x>>y&&x&&y) {map[x][y]=1;map[y][x]=1;m=max(m,x);m=max(m,y);}}int printf(){ int ans[maxn],t=0,i; i=k;tot++; while (d[i]!=0){ t++; ans[t]=d[i]; i=d[i]; } for (i=t;i>=1;i--) cout<<ans[i]<<" "; cout<<k; cout<<endl;}int dfs(int i){ if (i==k) {printf();return 0;} for (int j=1;j<=m;j++){ if (map[i][j]&&!vis[j]){ d[j]=i; vis[j]=1; dfs(j); vis[j]=0; } }}int main(){ int ti=0; while(cin>>k){ init(); ti++; cout<<"CASE "<<ti<<":"<<endl; int ok=0; for (int i=1;i<=m;i++) if (map[i][k]) ok=1; vis[1]=1; if (ok)dfs(1); cout<<"There are "<<tot<<" routes from the firestation to streetcorner "<<k<<"."<<endl; }}
做出来一个题没什么,重要的是做完后的反思,尤其是像我这种水过的,我的代码0.195s,严格来说还应该是TLE的代码
然后去网上看别人的思路与想法结合自己的反思
直接copy原话:
裸搜会超时的题目,其实题目的数据特地设计得让图稠密但起点和终点却不相连,所以直接搜索过去会超时。
只要判断下起点和终点能不能相连就行了,可以用并查集也可以用floyd算法,这样就能过了。
但是这个方法不是很完美的,如果两点之间只有一条线相连,而图又是稠密图,这样也很容易超时,数据强电就会挂掉。
可以把算法改进一下:是先从终点出发,无回溯的走遍和终点相连的所有点并标记,然后从起点出发,DFS判断下标记,这样就不会多走很多路了。另一个方法是在把点并入并查集的时候不考虑起点,然后DFS只走和终点同一集合的点。(这我联想到了前面的文章倒着bfs标记所有能达到的点的最短距离,这里n才20,用floyd遍历就可以了)
某位大神的博客上说Tarjan算法也可以很好的实现。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。