another 400ms n2solution……for HDU 4126. Genghis Khan the Conqueror

gistfile1.cpp

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>

typedef long long ll;
#define MAXX 3111
#define MAXE (MAXX<<1)
#define N 13
#define v to[i]
#define inf 0x3f3f3f3f
typedef std::pair<int,int>pii;

inline void min(int &a,int b){if(a>b)a=b;}

std::multiset<pii>q;

int map[MAXX][MAXX];
int val[MAXX][MAXX];
int up[MAXX][MAXX];

int pre[MAXX];
int dist[MAXX];
bool pm[MAXX][MAXX];
bool done[MAXX];

int fa[MAXX][N];
int dp[MAXX];

int edge[MAXX],nxt[MAXE],to[MAXE],cnt;
inline void add(int a,int b)
{
    nxt[++cnt]=edge[a];
    edge[a]=cnt;
    to[cnt]=b;
}

void dfs(int now,int f=0)
{
    fa[now][0]=f;
    for(int i(edge[now]);i;i=nxt[i])
        if(v!=f)
        {
            dp[v]=dp[now]+1;
            dfs(v,now);
        }
}

inline int lca(int a,int b)
{
    static int i,j;
    if(dp[a]<dp[b])
        std::swap(a,b);
    for(i=dp[a]-dp[b],j=0;i;i>>=1,++j)
        if(i&1)
            a=fa[a][j];
    if(a==b)
        return a;
    for(i=N-1;i>=0;--i)
        if(fa[a][i]!=fa[b][i])
        {
            a=fa[a][i];
            b=fa[b][i];
        }
    return fa[a][0];
}

inline void gao(int a,int b,int val)
{
    if(a==b)
        return;
    if(dp[a]<dp[b])
        std::swap(a,b);
//    printf("%d up %d %d\n",a,dp[a]-dp[b],val);
    min(up[a][dp[a]-dp[b]],val);
}

int n,m,i,j,k;
ll mst;
double ans;

void go(int now)
{
    for(int i(edge[now]);i;i=nxt[i])
        if(v!=fa[now][0])
        {
            go(v);
            for(j=1;j<n;++j)
            {
                min(up[now][j-1],up[v][j]);
                min(val[now][v],up[v][j]);
                min(val[v][now],up[v][j]);
            }
//            printf("se %d - %d %d\n",now,v,val[now][v]);
        }
    /*
    printf("in%d\n",now);
    for(j=1;j<n;++j)
        if(up[now][j]!=inf)
            printf("%d: up %d %d\n",now,j,up[now][j]);
    puts("");
    */
}

int main()
{
    while(scanf("%d %d",&n,&m),(n||m))
    {
        cnt=0;
        for(i=0;i<n;++i)
        {
            for(j=0;j<n;++j)
            {
                up[i][j]=val[i][j]=map[i][j]=inf;
                pm[i][j]=false;
            }
            dist[i]=inf;
            edge[i]=map[i][i]=pre[i]=0;
            done[i]=false;
        }
        while(m--)
        {
            scanf("%d %d %d",&i,&j,&k);
            map[i][j]=map[j][i]=k;
        }

        q.insert(pii(0,0));
        dist[0]=0;
        pre[0]=0;
        ans=0;
        while(!q.empty())
        {
            static pii now;
            now=*q.begin();
            q.erase(q.begin());
            if(now.first!=dist[now.second])
                continue;
            done[j=now.second]=true;
            ans+=dist[j];
            if(j)
            {
                pm[j][pre[j]]=pm[pre[j]][j]=true;
                add(j,pre[j]);
                add(pre[j],j);
            }
            for(i=0;i<n;++i)
                if(!done[i] && map[j][i]<dist[i])
                {
                    dist[i]=map[j][i];
                    pre[i]=j;
                    q.insert(pii(dist[i],i));
                }
        }
        mst=ans;
        dfs(0);
        for(i=1;i<N;++i)
            for(j=0;j<n;++j)
                fa[j][i]=fa[fa[j][i-1]][i-1];
        for(i=0;i<n;++i)
            for(j=i+1;j<n;++j)
                if(map[i][j]!=inf && !pm[i][j])
                {
                    k=lca(i,j);
                    gao(k,i,map[i][j]);
                    gao(k,j,map[i][j]);
                }
        go(0);
        /*
        for(i=0;i<n;++i)
            for(j=i+1;j<n;++j)
                if(pm[i][j])
                    printf("%d %d\n",i,j);
        printf("%lld\n",mst);
        */
        static int q;
        scanf("%d",&q);
        cnt=q;
        ans=0;
        while(q--)
        {
            scanf("%d %d %d",&i,&j,&k);
//            printf("%d %d: %d %d\n",i,j,val[i][j],map[i][j]);
            if(pm[i][j])
            {
                ans+=mst+std::min(val[i][j],k)-map[i][j];
//                printf("%lld\n",mst+std::min(val[i][j],k)-map[i][j]);
            }
            else
            {
                ans+=mst;
//                printf("%lld\n",mst);
            }
        }
        printf("%.4lf\n",ans/cnt);
    }
    return 0;
}