题意

给定\(n\)个点和\(m\)条无向边（\(n\le 3000\)），需要将这\(n\)个点连通。但是有\(Q\)次（\(Q\le 10^4\)）等概率的破坏，每次破坏会把\(m\)条边中的某条边的权值增大某个值，求\(Q\)次破坏每次将\(n\)个点连通的代价的期望？（全题的数据范围在int内可以过）

分析

这题是真的牛逼，我看了七八个博客都没看太明白，大多数人都没讲在点子上，但是还是有几篇博客不错的，参考如下：

参考A：https://blog.csdn.net/u014664226/article/details/49333081

参考B：https://blog.csdn.net/Anxdada/article/details/81086041

参考C：https://blog.csdn.net/ramay7/article/details/52236040 （这个是最好的，强烈推荐）

参考D：https://blog.csdn.net/gatevin/article/details/47042021 （有一些“实质上”的东西）

接下来说说我综合这些参考后自己对这题的理解与做法。

求期望的意思是，将每次破坏后的最小生成树的代价累加除以\(Q\)。然后我们仔细思考一下这个破坏。首先，如果更改发生在不是最小生成树上的边上，那么答案是不需要改变的。重点是改变发生在这棵生成树上的边中的情况下。此时这棵最小生成树会分成两棵树。显然地，新图的最小生成树一定包含这两棵树上的所有边。问题于是转化为原来的最小生成树被切成两棵树之后，如何选择权值最小的一条边将两棵树连通。

这里因此运用了树形dp。这里比较精彩：

我们记\(dp[i][j]\)是切断\((i,j)\)边后，i与j两个所在点的集合间的最短距离。但是我们不去直接这么搜索，而是去搜索i所在树的树根与j所在子树的每一个点的最短距离。于是我们将每个点当作树根进行DFS，在更新（搜索）时，我们用j所在子树所有点同root的直接距离更新掉dp数组，并有意归避掉\((i,j)\)边。可以想见，当第\(i\)轮更新完成，dp中一定保存了第1个到第\(i\)个root到他们相关点的最短距离。那么对每个点都dp过后，最后dp数组里面一定保存的就是我们要的东西了。

最后对每个查询做修正就可以了，具体见代码。真实树形dp+最小生成树好题，就是做的头疼，哈哈。

代码

/* ACM Code written by Sam X or his teammates.

 * Filename: hdu4126.cpp

 * Date: 2018-11-18

 */

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)

#define per(i,a,b) for(repType i=(a); i>=(b); --i)

#define ZERO(x) memset(x, 0, sizeof(x))

#define MS(x,y) memset(x, y, sizeof(x))

#define ALL(x) (x).begin(), (x).end()

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

using pi=pair<int,int>;

using repType=int;

using ll=long long;

using ld=long double;

using ull=unsigned long long;

int n,m;

struct Edge

{

    int u,v,w;

    Edge() {}

    Edge(int _u,int _v, int _w):

        u(_u), v(_v), w(_w) {}

    bool operator < (const Edge& rhs) const

    {

        if(w==rhs.w)

        {

            return u<rhs.u;

        }

        else return w<rhs.w;

    }

};

const int MAXN=3005;

vector<Edge> edges;

int mat[MAXN][MAXN];

int used[MAXN][MAXN];

int edges_ord[18000005];

int pa[MAXN];

vector<Edge> nedges;

vector<int> nG[MAXN];

inline void nadd_edge(int u,int v,int w)

{

    nedges.PB(u,v,w);

    nG[u].PB(int(nedges.size())-1);

}

int find_pa(int x)

{

    return pa[x]==x?x:pa[x]=find_pa(pa[x]);

}

inline void union_pa(int x,int y)

{

    int fx=find_pa(x),

        fy=find_pa(y);

    if(fx!=fy) pa[fx]=fy;

}

inline int kruskal()

{

    int ret=0;

    iota(pa,pa+n,0);

    sort(ALL(edges));

    rep(i,0,edges.size()-1)

    {

        int u=edges[i].u,

            v=edges[i].v,

            w=edges[i].w;

        if(find_pa(u)!=find_pa(v))

        {

            union_pa(u,v);

            ret+=w;

            used[u][v]=used[v][u]=w;

            nadd_edge(u,v,w);

            nadd_edge(v,u,w);

        }

    }

    return ret;

}

int dp[MAXN][MAXN];

int dfs(int root, int now, int pre)

{

    //cout<<root<<" "<<now<<" "<<pre<<endl;

    int ans=INF;

    rep(i,0,int(nG[now].size())-1)

    {

        int& v=nedges[nG[now][i]].v;

        if(v!=pre)

        {

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

            ans=min(ans,tmp);

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

        }

    }

    if(root!=pre && pre!=-1)

    {

        ans=min(ans, mat[now][root]);

    }

    return ans;

}

inline void init()

{

    edges.clear();

    nedges.clear();

    rep(i,0,n-1) nG[i].clear();

    MS(dp,0x3f);

    MS(used,-1);

    MS(mat,0x3f);

}

int main()

{

    while(scanf("%d%d",&n,&m)==2)

    {

        if(!n && !m) break;

        init();

        rep(i,0,m-1)

        {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            edges.PB(u,v,w);

            mat[u][v]=mat[v][u]=w;

        }

        int sum=kruskal();

        rep(i,0,n-1)

            dfs(i,i,-1);

        int q;

        scanf("%d",&q);

        double ans=0;

        rep(i,0,q-1)

        {

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            if(used[u][v]!=-1) ans+=sum-used[u][v]+min(dp[u][v], w);

            else ans+=sum;

        }

        printf("%.4lf\n",ans/(1.0*q));

    }

    return 0;

}

巴特西

「日常训练」 Genghis Khan the Conqueror（HDU-4126）

题意

分析

代码

最新文章

热门文章