BUPT 2017 Summer Training (for 16) #3G

題意

擺好的多米諾牌中有n個(gè)關(guān)鍵牌，兩個(gè)關(guān)鍵牌之間有邊代表它們之間有一排多米諾牌。從1號(hào)關(guān)鍵牌開(kāi)始推倒，問(wèn)最后倒下的牌在哪里，以及時(shí)刻。

題解

注意最后倒下的可能不是關(guān)鍵牌，而是關(guān)鍵牌之間的牌。
dfs找出每個(gè)關(guān)鍵牌最早到達(dá)的時(shí)間，也就是它們倒下的時(shí)刻。然后再對(duì)每條邊，計(jì)算邊上最后倒下的牌的時(shí)間。
其實(shí)就是跑一遍最短路。

代碼

#include <cstdio> #include <cstring> #include <algorithm> #define N 100001 #define inf 0x3f3f3f3f using namespace std; struct edge{int to,next;double w; }e[N<<1]; int head[N],cnt; void add(int u,int v,int w){e[++cnt]=(edge){v,head[u],(double)w};head[u]=cnt; } int n,m; int test; bool one; int last, second; double idx[N]; double ans; void dfs(int x,int fa){for(int i=head[x];i;i=e[i].next){int v=e[i].to;if(v==fa)continue;if(idx[x]+e[i].w<idx[v]){idx[v]=idx[x]+e[i].w;dfs(v,x);}} } int main(){while(scanf("%d%d",&n,&m),n||m){cnt=1;memset(head,0,sizeof head);for(int i=1,a,b,l;i<=m;++i){scanf("%d%d%d",&a,&b,&l);add(a,b,l);add(b,a,l);}printf("System #%d\n",++test);for(int i=2;i<=n;++i)idx[i]=1000000000.0;dfs(1,0);ans=-1;one=true;for(int i=1;i<=n;++i){if(idx[i]>ans){ans=idx[i];last=i;}}for(int i=2;i<=cnt;++i){double time=(idx[e[i].to]+idx[e[i^1].to]+e[i].w)*1./2;if(time>ans){ans=time;one=false;last=e[i].to;second=e[i^1].to;}}printf("The last domino falls after %.1f seconds, ", ans);if(one)printf("at key domino %d.\n", last);else{if(last>second)swap(last,second);printf("between key dominoes %d and %d.\n", last, second);}puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的「POJ 1135」Domino Effect（dfs）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。