UVA- 1504 - Genghis Khan the Conqueror(最小生成树-好题)

时间：2022-01-12 05:49:40

题意：

n个点，m个边，然后给出m条边的顶点和权值，其次是q次替换，每次替换一条边，给出每次替换的边的顶点和权值，然后求出这次替换的最小生成树的值;

最后要你输出:q次替换的平均值。其中n<3000，q<10000。

分析：

我们可以先求最小生成树，对于最小生成树的每一条边，我们要找到它的最佳替代边，使其价值最小。

具体实践方法：

树形dp，从每个点dfs一次，每次把i当成根，其余都是它的孩子，更新dp数组，对于i点为根的除j之外的所有的

子树中的所有点到j距离最小值。每次从一个点root开始dfs，搜索到最后一个叶子，开始看G[root][u]的大小，保证（root，u）

不是MST上的的边，那么一路返回，连接叶子节点的那条边的最佳替换边就是G[root][u]的大小，再继续返回，

此过程要看,map[root][...]的大小，其中[...]表示从叶子节点一路返回过来的点。

// File Name: 1504.cpp

// Author: Zlbing

// Created Time: 2013/6/17 19:36:53

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

#include<set>

#include<map>

#include<vector>

#include<cstring>

#include<stack>

#include<cmath>

#include<queue>

using namespace std;

#define CL(x,v); memset(x,v,sizeof(x));

#define INF 0x3f3f3f3f

#define LL long long

#define REP(i,r,n) for(int i=r;i<=n;i++)

#define RREP(i,n,r) for(int i=n;i>=r;i--)

const int MAXN=;

struct Edge{

    int u,v,cost;

    bool operator <(const Edge &rsh)const{

        return cost<rsh.cost;

    }

};

vector<Edge>edges;

vector<int> mst[MAXN];

int gmst[MAXN][MAXN];

int f[MAXN];

int dp[MAXN][MAXN];

int G[MAXN][MAXN];

    int n,m,Q;

    int ans=;

int find(int x)

{

    return f[x]==x?x:f[x]=find(f[x]);

}

void kruscal()

{

    ans=;

    CL(gmst,);

    for(int i=;i<=n;i++)f[i]=i;

    for(int i=;i<m;i++)

    {

        Edge e=edges[i];

        int fu=find(e.u);

        int fv=find(e.v);

        if(fu!=fv)

        {

            ans+=e.cost;

            f[fu]=fv;

            mst[e.u].push_back(e.v);

            mst[e.v].push_back(e.u);

            gmst[e.u][e.v]=gmst[e.v][e.u]=;

        }

    }

}

int dfs(int root,int u,int fa)

{

    int s=INF;

    for(int i=;i<mst[u].size();i++)

    {

        int v=mst[u][i];

        if(v==fa)continue;

        int tmp=dfs(root,v,u);

        s=min(s,tmp);

        dp[u][v]=dp[v][u]=min(dp[u][v],tmp);

    }

    if(root!=fa)//保证这条边不是生成树的边

        s=min(s,G[root][u]);

    return s;

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        if(n==)break;

        edges.clear();

        int a,b,c;

        REP(i,,n)mst[i].clear();

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

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

            {

                dp[i][j]=INF;

                G[i][j]=INF;

            }

        REP(i,,m)

        {

            scanf("%d%d%d",&a,&b,&c);

            edges.push_back((Edge){a,b,c});

            G[a][b]=G[b][a]=c;

        }

        sort(edges.begin(),edges.end());

        kruscal();

        REP(i,,n-)

        dfs(i,i,-);

        int sum=;

        scanf("%d",&Q);

        REP(i,,Q)

        {

            scanf("%d%d%d",&a,&b,&c);

            if(!gmst[a][b])

                sum+=ans;

            else

                sum+=ans*1.0-G[a][b]+min(dp[a][b],c);

        }

        double s=sum/(double)Q;

        printf("%.4lf\n",s);

    }

    return ;

}

相关文章