首页 > 代码库 > hdu4126(最小生成树+dfs)

hdu4126(最小生成树+dfs)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4126

题意:给出一幅3000个点的图,有10000次操作: 求将某条边的权值变大后的最小生成树,最后输出10000次操作得到的最小生成树权值的平均值。

分析:

对于每次询问, 都是将a,b之间的边增加到c, 会出现 两种情况:

1. 如果边权增加的那条边原先就不在最小生成树中,那么这时候的最小生成树的值不变

2. 如果该边在原最小生成树中,那么这时候将增加的边从原最小生成树中去掉,这时候生成树就被分成了两个各自联通的部分,可以证明的是,这时候的最小生成树一定是将这两部分联通起来的最小的那条边。

设dp[i][j]表示去掉最小生成树中的边(i,j)分成两个联通部分后,再次将他们再次连接起来的最小的那条边长。

那么对于每点pos开始往下dfs,不断维护一个dis[pos][u](u为树上的另一点)的最小值ans,搜完子树的子节点后让最小值ans=dp[u][v],因为断开边(u,v)后靠pos连接v子树上的某一节点使得以u和v为根节点的两颗子树再次连接起来。

 

技术分享
#pragma comment(linker,"/STACK:102400000,102400000")#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 3010#define FILL(a,b) (memset(a,b,sizeof(a)))using namespace std;struct edge{    int u,v,w;    bool operator<(const edge &a)const    {        return w<a.w;    }}e[N*N];int dis[N][N],dp[N][N],vis[N][N],fa[N];int n,m,q;vector<int>g[N];int find(int x){    return x==fa[x]?x:fa[x]=find(fa[x]);}void init(){    for(int i=0;i<n;i++)    {        fa[i]=i;g[i].clear();        for(int j=0;j<n;j++)            dis[i][j]=dp[i][j]=inf;    }    FILL(vis,0);}int kruskal(){    int res=0;    for(int i=0;i<m;i++)    {        int a=find(e[i].u);        int b=find(e[i].v);        if(a!=b)        {            fa[a]=b;            res+=e[i].w;            vis[e[i].u][e[i].v]=vis[e[i].v][e[i].u]=1;//uv这条边在最小生成树上            g[e[i].u].push_back(e[i].v);//构造最小生成树            g[e[i].v].push_back(e[i].u);        }    }    return res;}int dfs(int pos,int u,int fa){    int ans=inf;    for(int i=0,size=g[u].size();i<size;i++)    {        int v=g[u][i];        if(v==fa)continue;        int mn=dfs(pos,v,u);        ans=min(ans,mn);        dp[u][v]=dp[v][u]=min(dp[u][v],mn);    }    //不断维护一个pos到v上的某一子节点的最小距离,保证边(u,v)断后ans为最优取代边,前提是(u,v)这条边不知最小生成树上    if(fa!=pos)ans=min(ans,dis[pos][u]);    return ans;}int main(){    int a,b,c;    while(scanf("%d%d",&n,&m)>0)    {        if(m+n==0)break;        init();        for(int i=0;i<m;i++)        {            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);            dis[e[i].u][e[i].v]=dis[e[i].v][e[i].u]=e[i].w;//点u点v的距离        }        sort(e,e+m);        int mst=kruskal();        for(int i=0;i<n;i++)        {            dfs(i,i,-1);        }        scanf("%d",&q);        double sum=0;        for(int i=0;i<q;i++)        {            scanf("%d%d%d",&a,&b,&c);            if(!vis[a][b])            {                sum+=mst;            }            else            {                sum+=mst-dis[a][b]+min(c,dp[a][b]);            }        }        printf("%.4lf\n",sum/q);    }}
View Code

 

hdu4126(最小生成树+dfs)