hdu 4126 MST的最佳替换边 —— 2011ACM福州赛区F题

这题AC的挺不容易的，花了很多时间，但是我觉得做完一道这种题能学到很多东西，绝对不是刷20道甚至是100道水题能比的~

这题的关键是在求出最小生成树之后求出去掉生成树任意一条边后剩下的两颗树的距离，可以证明这个距离就是最佳替换边的长度，而把原来最小生成树的边换成最佳替换边后所得到的生成树就是原图中去掉那条边的最小生成树，这个用反正法可以证明，如果新得到的树不是最小生成树可以推出原来的树也不是最小生成树，要画图我就不详细证了。

然后求两颗树之间的最小距离我是用树状dp实现的，挺麻烦的，dp的方法有很多，只要把复杂度控制在O（n2）之内就可以了~~

好吧，哥继续搞sgu了 ~

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;

#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif

#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a)         for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a)        for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define SZ(a)           ((int)a.size())
#define PP(n,m,a)       puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb              push_back
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)

const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-10;
const double pi = acos(-1.0);
const int maxn = 3011;

struct zz
{
    int from;
    int to;
    int cost;
    bool operator < (const zz & cmp ) const
    {
        return cost > cmp.cost;
    }
}zx;

priority_queue<zz>q;
vector<zz>g[maxn];
vector<int>t[maxn];

bool hash[maxn][maxn];
bool vis[maxn];
bool ist[maxn][maxn];
bool fd[maxn][maxn];
int d[maxn][maxn];
int dp[maxn][maxn];
int ex[maxn];
int f[maxn];
int n,m,qq;
int mst;

void init()
{
    FF(i,maxn)
    {
        g[i].clear();
        t[i].clear();
    }
    CL(q);
    MM(hash,false);
    MM(fd,false);
    return ;
}

int prim()
{
    int ans = 0;
    CL(q);
    MM(vis,false);
    MM(f,-1);
    MM(ist,false);
    vis[0]=true;
    FF(i,g[0].size())
    {
        q.push(g[0][i]);
    }
    int now,to;
    int temp;
    FOR(i,1,n-1)
    {
        while(true)
        {
            zx = q.top();
            q.pop();
            if(vis[zx.to])
            {
                continue;
            }
            f[zx.to] = zx.from;
            ans += zx.cost;
            ist[zx.from][zx.to] = ist[zx.to][zx.from] = true;
            t[zx.from].push_back(zx.to);
            vis[zx.to]=true;
            now = zx.to;
            FF(i,g[now].size())
            {
                to = g[now][i].to;
                if(!vis[to])
                {
                    q.push(g[now][i]);
                }
            }
            break;
        }
    }
    return ans;
}

void dfs(short now)
{
    vis[now] = true;
    short i;
    for(i=0;i<n;i++) if(vis[i])
    {
        fd[now][i] =true;
    }
    short to;
    for(i=0;i<g[now].size();i++)
    {
        to = g[now][i].to;
        if(!vis[to] && f[to]!=now)
        {
            dp[now][to] = g[now][i].cost;
        }
    }
    for(i=0;i<t[now].size();i++)
    {
        to = t[now][i];
        dfs(to);
    }
    vis[now]=false;
    return ;
}

int dpst(short now,short id)
{
    short to;
    if(fd[id][now])
    {
        FF(i,t[now].size())
        {
            to = t[now][i];
            dpst(to,id);
        }
    }
    else
    {
        int temp = inf;
        FF(i,t[now].size())
        {
            to = t[now][i];
            temp = min( dpst(to,id) , temp );
        }
        dp[id][now] = temp = min(dp[id][now],temp);
        return temp;
    }
}

void final()
{
    FF(i,n) FF(j,n) if(!fd[j][i])
    {
        ex[i] = min(ex[i],dp[j][i]);
    }
    return ;
}

void start()
{
    FF(i,maxn) ex[i] = inf;
    mst = prim();
    FF(i,maxn) FF(j,maxn)
    {
        dp[i][j] = inf;
    }
    MM(vis,false);
    dfs(0);
    FF(i,n)
    {
        dpst(0,i);
    }
    final();
    return ;
}

int main()
{
    while(cin>>n>>m)
    {
        if(!n && !m)
        {
            break;
        }
        init();
        FF(i,m)
        {
            SS(zx.from);
            SS(zx.to);
            SS(zx.cost);
            hash[zx.from][zx.to] = hash[zx.to][zx.from] = true;
            d[zx.from][zx.to] = d[zx.to][zx.from] = zx.cost;
            g[zx.from].push_back(zx);
            swap(zx.from,zx.to);
            g[zx.from].push_back(zx);
        }
        start();
        cin>>qq;
        int x,y,z;
        double ans=0.0;
        double add;
        double qx = qq;
        while(qq--)
        {
            SS(x);
            SS(y);
            SS(z);
            if(!ist[x][y])
            {
                ans += mst;
            }
            else
            {
                if(f[x] == y)
                {
                    add = min(ex[x],z) - d[x][y];
                }
                else
                {
                    add = min(ex[y],z) - d[x][y];
                }
                ans += add + mst;
            }
        }
        ans /= qx;
        printf("%.4lf\n",ans);
    }
    return 0;
}