正題

鏈接 需要紀(jì)中OJ賬號
有n條木棒，長度為1或根號2，給出每根木棒兩頭的坐標(biāo)，和燃燒需要的時間。只能從一個木棒的一頭開始點火，求燃燒完所有木棒所需要的最短時間。

---

輸入輸出（需要自取）

Input

輸入文件第一行為一個正整數(shù)N，表示組成圖形的木棍數(shù)目，后面共有N行，每行5個數(shù)： X1 Y1 X2 Y2 T,其中（X1, Y1）和（X2, Y2）分別表示木棍兩端的坐標(biāo)，T表示木棍燃燒時間，是指從木棍的某一端點火燃燒到別一端，燃完所需的時間。

Output

輸出文件是一個保留4位小數(shù)的實數(shù)，表示所有木棍完全燃燒的最少時間。

Sample Input

輸入1：

1
0 0 1 1 1

輸入2：

5
0 0 0 1 1
1 0 0 1 10
0 0 1 0 1
0 0 1 1 1
2 2 1 1 1

輸入3：

3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50

Sample Output

輸出1：

1.0000

解釋：

從任一端點火都行，燃燒時間都是1

輸出2：

3.2500

解釋：

在 (0,0)位置點火木棍 1, 3 和 4 將被點燃，燃燒0.5分鐘后，木棍2將被從中間點燃向兩端燃燒，再過0.5分鐘，木棍1, 3, 4 將被完全燃燒，木棍5 將被點燃并在1分鐘后燃燒完 (比木棍2早燃完)。 　　木棍2從中間向兩端燃燒0.5分鐘以后，變成兩小段，每段的燃燒時間是4.5 分鐘。但因為此時兩小段木棍的另一端也同時被點燃，燃燒速度變成原來的兩倍，還需2.25 分鐘的燃燒時間， 所以總時間： 1 + 2.25 = 3.25

輸出3：

35.0000

解釋：

在 (1,2)位置點火， 木棍(1 1, 1 2) 和(1 2, 2 2)將燃燒 10 分鐘。. 最后一根木棍在10分鐘后從兩端被點燃，燃燒時間為25分鐘。

---

解題思路

木棒可能在中間相連的情況只能在中間，所有加入一下中間點就好了。然后用Floyd最短路算出每個點到其他點的距離，不過所有的點燒完不代表木棒被燒完，所有我們需要枚舉點開始燒的點，然后計算每個木棒需要燃燒的時間。

---

代碼

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int a[1601][1601],n,x1,x2,x3,y1,y2,y3,m,wn; bool mid[501]; double dis[501][501],mins,maxs,lon,ans,e[501][501]; int main() {for (int i=0;i<=500;i++)for (int j=0;j<=500;j++){dis[i][j]=2147483647;e[i][j]=2147483647;}scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d%d%d%d%lf",&x1,&y1,&x2,&y2,&lon);x1+=400;x2+=400;y1+=400;y2+=400;//轉(zhuǎn)換為正數(shù)x1*=2;x2*=2;x3=(x1+x2)/2;y1*=2;y2*=2;y3=(y1+y2)/2;//求中間的坐標(biāo)lon/=2;//分為兩條木棍if (!a[x1][y1]){m++;//加入新坐標(biāo)a[x1][y1]=m;//表示該坐標(biāo)的點編號}if (!a[x2][y2]){m++;a[x2][y2]=m;}if (!a[x3][y3]){m++;a[x3][y3]=m;mid[m]=true;}dis[a[x1][y1]][a[x3][y3]]=lon;dis[a[x3][y3]][a[x1][y1]]=lon;dis[a[x2][y2]][a[x3][y3]]=lon;dis[a[x3][y3]][a[x2][y2]]=lon;//記錄e[a[x1][y1]][a[x3][y3]]=lon;e[a[x3][y3]][a[x1][y1]]=lon;e[a[x2][y2]][a[x3][y3]]=lon;e[a[x3][y3]][a[x2][y2]]=lon;}for (int k=1;k<=m;k++)for (int i=1;i<=m;i++)for (int j=1;j<=m;j++){if (dis[i][k]<2147483647 && dis[k][j]<2147483647)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//計算最短路}mins=2147483647;for (int k=1;k<=m;k++){if(mid[k]) continue; //排除在中間點ans=0;for (int i=1;i<=m;i++) ans=max(dis[k][i],ans);//取所有點燒完的所需時間for (int i=1;i<=m;i++)for (int j=i+1;j<=m;j++){if(e[i][j]<2147483647)if (dis[k][i]<e[i][j]+dis[k][j] && dis[k][j]<dis[k][i]+dis[i][j])//是否相接{ans=max(ans,max(dis[k][i],dis[k][j])+(e[i][j]-max(dis[k][i],dis[k][j])+min(dis[k][i],dis[k][j]))/2.0);//計算該木棒燃燒時間取最大值}}mins=min(ans,mins);//取最少的時間}printf("%.4lf",mins); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【2018.3.17】模拟赛之四-ssl1864jzoj1368 燃烧木棒【最短路，Floyd】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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