【图论杂题】：D.fire [Floyed+巧妙建图]

题目：

团队链接：fire

题面：

$Tom$是调皮的孩子，特别喜欢玩火，现在他手上有若干根长度分别为$1$和$\sqrt{2}$的木棍,还有一张不能燃烧的平板，他把平板划分成长度为$1$的单元格，并标上座标。然后按以下规则把平板上的木棍组成一个连通图：木棍的两端必须放在单元格的顶点上。即长度为1的木棍放在单元格的某一边上，长度为$\sqrt{2}$的木棍放在单元格的对角线上。
$Tom$的点火规则是，只能从木棍的两端点火，而不能从木棍的中间点火。如图，不能在$A$点点火，但在$C$点或$B$点点火都是充许的。点火后，火会沿着木棍向前燃烧(每根都有自己的燃烧速度)，、并能点燃与它相接的其它木棍。
求所有木棍完全燃烧的最少时间。(保留4位小数的实数)
范围：
$1\le n\le 40,?200\le X_1,Y_1,X_2,Y_2\le 200$;

$0\le T\le 10^7$

输入格式：

第一行为一个正整数N，表示组成图形的木棍数目，后面共有N行，每行5个数： X1 Y1 X2 Y2 T,其中（X1, Y1）和（X2, Y2）分别表示木棍两端的坐标，T表示木棍燃烧时间，是指从木棍的某一端点火燃烧到别一端，燃完所需的时间。

输出格式：

一个保留4位小数的实数，表示所有木棍完全燃烧的最少时间。

样例1：

输入：

1
0 0 1 1 1

输出：

1.0000

样例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.2500

样例3：

输入：

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

输出：

35.0000

题解：

（这个题啊，表示想了好长时间，，尽管看了题解，）
其实不是很难，重要在建图，把图中的每根火柴变成两根，由于在点燃的时候就能比较好处理了，在A处就特判一下就行了，这样就把问题转化为木棍和木棍之间只能在木根的两端点相交。然后再以木棍为边，木棍与木棍之间的交点为顶点，构建一个连通图，所以问题就转化为寻找一个合适的顶点使得燃烧以后完全燃烧的时间最短，很显然就是点燃顶点到图中最远点的时间。
看一下$n$的范围就知道，，Floyed啊，用Floyed求的是第i个点的燃烧时间，但是有一个很完美的BUG是比较不容易想到的，（如图）

这就是一个很特殊的情况，就还是在点都烧完的时候还有之间的边烧不完，这就很尴尬，，，
怎么解决呢，，，特判处理不就行了，，，，
（重点看注释吧，尽管不是很多，，，(^_?)☆）

#include<bits/stdc++.h>
#define D double 
using namespace std;
inline int read()
{
    int s=0,w=1; char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int ocean=1e7+7;
const int sea=500;
const int pool=200;
struct idn{
    int x,y;}dd[sea];
struct see{
    int x,ver;D edge;}e[sea];
int n,tot,idn,d[pool][pool],f[pool][pool];
D dis[pool][pool],ans=ocean,res,g[sea];
int add_d(int x,int y,bool ins)
{
    if(d[x][y]) return d[x][y];d[x][y]=++idn,dd[idn].x=x,dd[idn].y=y,f[x][y]=ins; return idn;
}
void add_e(int x,int y,int w){
    e[++tot].x=x;e[tot].ver=y;e[tot].edge=w*0.5;}
int main()
{
    n=read(); for(int i=1;i<=n;i++){
    int x1=read(),y1=read(),x2=read(),y2=read(),w=read();int xx,yy,mm;xx=add_d(sea+x1*2,sea+y1*2,1);yy=add_d(sea+x2*2,sea+y2*2,1);mm=add_d(sea+x2+x1,sea+y2+y1,0);add_e(mm,xx,w); add_e(mm,yy,w);}//建图for(int i=1;i<=idn;i++) for(int j=1;j<=idn;j++) dis[i][j]=ocean;for(int i=1;i<=idn;i++) dis[i][i]=0;for(int i=1;i<=tot;i++){
     int x=e[i].x,y=e[i].ver;D z=e[i].edge;dis[x][y]=min(dis[x][y],z),dis[y][x]=min(dis[y][x],z);}//Floyedfor(int k=1;k<=idn;k++)for(int i=1;i<=idn;i++)for(int j=1;j<=idn;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);for(int i=1;i<=idn;i++){
    int x=dd[i].x,y=dd[i].y;if(!f[x][y]) continue; res=0;for(int j=1;j<=idn;j++) res=max(res,(g[j]=dis[i][j]));for(int j=1;j<=tot;j++){
    int x=e[j].x,y=e[j].ver;D z=e[j].edge;D cc=abs(g[x]-g[y]);if(cc>=z) continue;//判断是不是按个优秀的BUGD ff=0.5*(z-cc);//乘的时候乘一半就行了，另一半还会再加res=max(res,max(g[x],g[y])+ff);}ans=min(res,ans);}printf("%.4f\n",ans);return 0;
}

Continue……