HDUOJ 5723 Abandoned country

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

题意:给你n个节点和m条边求最小花费的方案,每个节点之间都可以相连接,然后求两两之间节点距离的数学期望。

思路:前者跑一下最小生成树就可以了,然后重新建图。对于距离的期望我们可以容易得出以下式子

\sum_{i=1}^{n}\sum_{j=1}^{n}d\left[i \right]+d\left[j \right]-2*d\left[lca\left(i,j \right) \right]\left(i\neq j \right)

,化简得

2*\left(n-1 \right)*\sum_{i=1}^{n}d\left[i \right]-4*\sum_{i=1}^{n}d\left[i \right]*lca\left[i \right]

,其中lca\left(i\right)表示i作为lca的次数,dfs的时候统计一下最后除以n*(n-1)就是期望了。

#include<bits/stdc++.h>
#define MOD 1e9+7
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef __int64 ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T>inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Node{
    int v,w;
    Node(int _,int __):v(_),w(__){}
};
vector<Node>G[maxn];
int T,n,m;
ll ans;
ll lca[maxn],dis[maxn];
int sz[maxn];
void init(){
    ans=0;
    for (int i=0;i<maxn;i++) G[i].clear();
}
void dfs(int u,int f,ll sum){
    dis[u]=sum;
    lca[u]=0;
    sz[u]=1;
    for (int i=0;i<(int)G[u].size();i++){
        Node &e=G[u][i];
        if (e.v==f) continue;
        dfs(e.v,u,sum+e.w);
        lca[u]+=1LL*sz[u]*sz[e.v];
        sz[u]+=sz[e.v];
    }
}
struct Edge{
    int u,v,cost;
    Edge(int u,int v,int cost):u(u),v(v),cost(cost){}
    bool operator < (const Edge& rhs) const{
        return cost<rhs.cost;
    }
};
struct Kruskal{
    int n,m;
    vector<Edge>edges;
    int fa[maxn];
    int Find(int x) {return fa[x]==-1?x:fa[x]=Find(fa[x]);}

    void init(int n){
        this->n=n;
        m=0;
        memset(fa,-1,sizeof(fa));
        edges.clear();
    }

    void AddEdge(int u,int v,int cost){
        edges.push_back(Edge(u,v,cost));
        m=edges.size();
    }

    ll kruskal(){
        ll sum=0;
        int cnt=0;
        sort(edges.begin(),edges.end());

        for (int i=0;i<m;i++){
            int u=edges[i].u,v=edges[i].v;
            int tx=Find(u),ty=Find(v);
            if (tx!=ty){
                sum+=1LL*edges[i].cost;
                G[u].push_back(Node(v,edges[i].cost));
                G[v].push_back(Node(u,edges[i].cost));
                fa[tx]=ty;
                if (++cnt>=n-1) break;
            }
        }

        return sum;
    }
}KK;

int main(){
    for (read(T);T;T--){
        read(n),read(m);
        if (n==0 || m==0){
            printf("0 0.00\n");
            continue;
        }
        init();
        KK.init(n);
        for (int i=1;i<=m;i++){
            int u,v,w;read(u),read(v),read(w);
            KK.AddEdge(u,v,w);
        }
        ll anss=KK.kruskal();
        dfs(1,0,0);
        for (int i=1;i<=n;i++){
            ans+=2*(n-1)*dis[i]-4*lca[i]*dis[i];
        }
        double t=n*(n-1.0);
        printf("%I64d %.2lf\n",anss,(double)ans/t);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注