[最短路徑]NOIP模擬題：燃燒木棍 fire 解題報告

【問題描述】
Tom 是調皮的孩子，特別喜歡玩火，現在他手上有若干根長度分別爲 1 和sqrt(2) 的木棍，還有一張不能燃燒的平板，他把平板劃分成長度爲 1 的單元格，並標上座標。然後按以下規則把平板上的木棍組成一個連通圖：木棍的兩端必須放在單元格的頂點上。即長度爲 1 的木棍放在單元格的某一邊上，長度爲sqrt(2) 的木棍放在單元格的對角綫上。

Tom 的點火規則是，只能從木棍的兩端點火，而不能從木棍的中間點火。 如圖 ，不能在 A 點點火，但在 C 點或 B 點點火都是充許的。點火後，火會沿着木棍向前燃燒（每根都有自己的燃燒速度），並能點燃與它相接的其它木棍。
任務： 寫一程序計算從哪裏開始點火，使得燃燒的總時間最短，輸出最短時間。
Input Data
輸入文件第一行爲一個正整數 N ，表示組成圖形的木棍數目，後面共有 N 行，每行 5 個數： X1 Y1 X2 Y2 T , 其中（ X1 , Y1 ） 和（ X2 , Y2 ）分別表示木棍兩端的座標， T 表示木棍燃燒時間，是指從木棍的某一端點火燃燒到別一端，燃完所需的時間。
Output Data
輸出文件是一個保留 4 位小數的實數，表示所有木棍完全燃燒的最少時間。
約束
1 ≤n≤40
保證圖形是連通的，所有的木棍長度都是 1 或sqrt(2) ，沒有任何兩根木棍重合 .
-200≤ X1, Y1, X2, Y2 ≤200; 0≤ T ≤ 10^7 .
如果你的輸出結果與標準答案相差小於 0.001 ，則認爲你的結果正確。
樣例 1
fire.in
1
0 0 1 1 1
fire.out
1.0000
解釋：從任一端點火都行，燃燒時間都是 1
樣例 2
fire.in5
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
fire.out 
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
fire.in3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50
fire.out  
35.0000
解釋：在 (1,2) 位置點火， 木棍 (1 1, 1 2) 和 (1 2, 2 2) 將燃燒 10 分鐘。 . 最後一根木棍在 10 分鐘後從兩端被點燃，燃燒時間爲 25 分鐘。
【分析】
Floyd算法求最短路，只是構圖很困難罷了。
具體算法的PPT課件下載：http://zhuyifan.net84.net/ppt/fire.ppt
【我的代碼】
/*
*Problem: 燃燒木棍   fire
*Author: Yee-fan Zhu
*Date: Dec.01.2011
*Website: www.zyfworks.tk
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int N;

double max(double x,double y)
{
    if(y>x)
        x=y;
    return x;
}


class Wood
{
public:
    double x1,x2;
    double y1,y2;
    double time;
}F[42];
   
class Point
{
public:
    double x,y;
}P[1000];

Wood W[1000];
int D=0;
   
int M=0;
double Mat[1002][1002];   
int Used[2000][2000];
const int add=500;

void init()
{
    std::ios::sync_with_stdio(false);
    scanf("%d\n",&N);
    for (int i=-450;i<=1050;i++)
        for (int j=-450;j<=1050;j++)
            Used[i+add][j+add]=-1;
    for (int i=1;i<=300;i++)
        for (int j=1;j<=300;j++)
            Mat[i][j]=10000000;
    for (int i=1;i<=300;i++)
        Mat[i][i]=0;
    for (int i=1;i<=N;i++)
    {
        scanf("%lf %lf %lf %lf %lf\n",&F[i].x1,&F[i].y1,&F[i].x2,&F[i].y2,&F[i].time);
    }
    double x1,x2,y1,y2,t;
    for (int i=1;i<=N;i++)
    {
        x1=F[i].x1,y1=F[i].y1;
        x2=F[i].x2,y2=F[i].y2;
        t=F[i].time;
       
        int p1,p2;
        p1=Used[int(x1*2)+add][int(y1*2)+add];
        p2=Used[int(x2*2)+add][int(y2*2)+add];
        if(p1==-1)
        {
            M++;
            Used[int(x1*2)+add][int(y1*2)+add]=M;
            P[M].x=x1,P[M].y=y1;
            p1=M;
        }
       
        if(p2==-1)
        {
            M++;
            Used[int(x2*2)+add][int(y2*2)+add]=M;
            P[M].x=x2,P[M].y=y2;
            p2=M;
        }
       
        Mat[p1][p2]=t;
        Mat[p2][p1]=t;
        bool flag=true;
        if(F[i].x1-F[i].x2==0 || F[i].y1-F[i].y2==0)
        {
            D++;
            W[D].x1=x1,W[D].y1=y1;
            W[D].x2=x2,W[D].y2=y2;
            W[D].time=t;
            continue;
        }
        double x3,y3;
        double x4,y4;
        if((x1>x2 && y1>y2 )||(x1<x2 && y1<y2 ))
        {
            if(x1>x2 && y1>y2 )
            {
                x3=x1-1;
                y3=y1;
                x4=x1;
                y4=y1-1;
            }
            if(x1<x2 && y1<y2)
            {
                x3=x1;
                y3=y1+1;
                x4=x1+1;
                y4=y1;
            }
        }
        else
        {
            if(x1<x2 && y1>y2)
            {
                x3=x1;
                y3=y1-1;
                x4=x1+1;
                y4=y1;
            }
            if(x1>x2 && y1<y2)
            {
                x3=x1-1;
                y3=y1;
                x4=x1;
                y4=y1+1;
            }
        }
        for (int j=1;j<=N;j++)
        {
            if((F[j].x1==x3 && F[j].y1==y3 && F[j].x2==x4 &&F[j].y2==y4) || (F[j].x1==x4 && F[j].y1==y4 && F[j].x2==x3 &&F[j].y2==y3) )
            {
                double x5,y5;
                x5=double((x1+x2)/double(2));
                y5=double((y1+y2)/double(2));
                int p3=Used[int(x5*2)+add][int(y5*2)+add];
                if(p3==-1)
                {
                    M++;
                    p3=M;
                    P[M].x=x5,P[M].y=y5;
                    Used[int(x5*2)+add][int(y5*2)+add]=M;
                }
                Mat[p3][p1]=t/(double(2)),Mat[p1][p3]=t/(double(2));
                Mat[p2][p3]=t/(double(2)),Mat[p2][p3]=t/(double(2));
                D++;
                W[D].x1=x3,W[D].y1=y3;
                W[D].x2=x5,W[D].y2=y5;
                W[D].time=t/(double(2));
               
                D++;
                W[D].x1=x4,W[D].y1=y4;
                W[D].x2=x5,W[D].y2=y5;
                W[D].time=t/(double(2));
                flag=false;
                break;
            }
        }
       
        if(flag)
        {
            D++;
            W[D].x1=x1,W[D].y1=y1;
            W[D].x2=x2,W[D].y2=y2;
            W[D].time=t;
        }
    }
}

void Floyd()
{
    double tmp;
    for (int k=1;k<=M;k++)
    {
        for (int i=1;i<=M;i++)
        {
            for (int j=1;j<=M;j++)
            {
                tmp=Mat[i][k]+Mat[k][j];
                if(tmp<Mat[i][j])
                    Mat[i][j]=tmp;
            }
        }
    }
}

void work()
{
    double tot=100000000;
    for (int i=1;i<=M;i++)
    {
        double x,y;
        x=P[i].x;
        y=P[i].y;
        int tmp;
        tmp=int(x*2);
        if(tmp%2!=0)
            continue;
       
        int p=Used[int(x*2)+add][int(y*2)+add];
        double s=0;
        for (int j=1;j<=M;j++)
            s=max(s,Mat[p][j]);
       
        double x1,x2;
        double y1,y2;
        int p1,p2;
        double t1,t2;
        double dif;
        double need;
        for (int j=1;j<=D;j++)
        {
            x1=W[j].x1,y1=W[j].y1;
            x2=W[j].x2,y2=W[j].y2;
            p1=Used[int(x1*2)+add][int(y1*2)+add];
            p2=Used[int(x2*2)+add][int(y2*2)+add];
            t1=Mat[p][p1];
            t2=Mat[p][p2];
           
            double mint=t2;
            if(t1<mint)
                mint=t1;
               
            dif=max(t1-t2,t2-t1);
            if(dif>=W[j].time)
                continue;
            need=(W[j].time-dif)/(double(2));
            need=need+mint+dif;
            if(need>s)
                s=need;
        }
        if(s<tot)
            tot=s;
    }
    printf("%.4lf",tot);
}

int main()
{
    freopen("firez.in","r",stdin);
    freopen("firez.out","w",stdout);
    init();
    Floyd();
    work();
    return 0;
}