hdu4756 Install Air Conditioning(MST + 树形DP)

题目大意：给n个点，现在要使这n个点连通，并且要求代价最小。现在有2个点之间不能直接连通（除了第一个点），求最小代价。

题目分析：跟这题一样样的，唉，又是原题。。先求mst，然后枚举边，对于生成树上的边替换，用树形dp O(N^2)求出每条生成树边的最小替代边。然后替换后的最大值。

详情请见代码：

#include <iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<cctype>

#include<map>

#include<vector>

#include<set>

#include<queue>

#include<string>

using namespace std;

const int N = 1005;

const int M = 3000005;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

const double PI = acos(-1.0);

typedef __int64 ll;

double dis[N][N];

double dp[N][N];

bool used[N][N];

bool flag[N];

double lowcost[N];

int pre[N],head[N];

struct node

{

    int x,y;

}pt[N];

struct nd

{

    int to,next;

}e_mst[M];

int n,m,num;

double B;

void build(int s,int e)

{

    e_mst[num].to = e;

    e_mst[num].next = head[s];

    head[s] = num ++;

}

double getdis(int x1,int y1,int x2,int y2)

{

    return sqrt((double)(x1 - x2) * (double)(x1 - x2) + (double)(y1 - y2) * (double)(y1 - y2));

}

void prim()

{

    B = 0;

    int i,j;

    memset(flag,false,sizeof(flag));

    for(i = 1;i <= n;i ++)

    {

        lowcost[i] = dis[1][i];

        pre[i] = 1;

    }

    flag[1] = true;

    for(i = 1;i < n;i ++)

    {

        double Min = 100000000.0;

        int v;

        for(j = 1;j <= n;j ++)

        {

            if(flag[j] == false && lowcost[j] < Min)

            {

                Min = lowcost[j];

                v = j;

            }

        }

        B += Min;

        used[pre[v]][v] = used[v][pre[v]] = true;

        build(v,pre[v]);

        build(pre[v],v);

        flag[v] = true;

        for(j = 1;j <= n;j ++)

        {

            if(flag[j] == false && lowcost[j] > dis[v][j])

            {

                lowcost[j] = dis[v][j];

                pre[j] = v;

            }

        }

    }

}

double dfs(int cur,int u,int fa)

{

    double ret = inf;

    for(int i = head[u];~i;i = e_mst[i].next)

    {

        if(e_mst[i].to == fa)

            continue;

        double tmp = dfs(cur,e_mst[i].to,u);

        ret = min(tmp,ret);

        dp[u][e_mst[i].to] = dp[e_mst[i].to][u] = min(tmp,dp[u][e_mst[i].to]);

    }

    if(cur != fa)

        ret = min(ret,dis[cur][u]);

    return ret;

}

int main()

{

    int t,i,j;

    scanf("%d",&t);

    while(t --)

    {

        scanf("%d%d",&n,&m);

        for(i = 1;i <= n;i ++)

            scanf("%d%d",&pt[i].x,&pt[i].y);

        for(i = 1;i <= n;i ++)

            for(j = 1;j <= i;j ++)

            {

                dp[i][j] = dp[j][i] = inf;

                if(i == j)

                    dis[i][j] = 0;

                else

                    dis[i][j] = dis[j][i] = getdis(pt[i].x,pt[i].y,pt[j].x,pt[j].y);

            }

        memset(used,false,sizeof(used));

        memset(head,-1,sizeof(head));

        num = 0;

        prim();

        double ans = B;

        for(i = 0;i < n;i ++)

            dfs(i,i,-1);

        for(i = 2;i <= n;i ++)

        {

            for(j = 2;j < i;j ++)

            {

                if(used[i][j] == true)

                {

                    ans = max(ans,B-dis[i][j]+dp[i][j]);

                }

            }

        }

        printf("%.2lf\n",ans*m);

    }

    return 0;

}

//718MS	17100K