算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述: 

    求N<3,000个点的稠密图的最小生成树的每条边的最佳替换边。

算法分析:

    先求最小生成树,这个不用说了。

    dp[i][j]表示,i和i的子孙到j的最小边(不计算生成树的边)。
    这个可以通过树形DP(中序遍历 + 后序遍历)求的。
    注意j不能是i的子孙,这个要通过时间戳来判断。

    同时用一个优先级队列,把这样的边都存起来。在回溯过程中仅用O(logE)的时间就可以判断最佳边了。
    复杂度O(V*V*logE)
    写起来不太好写,想到不难,但是复杂度不好把握。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
// graph
const int V = 3000+10;
int n,m, num[V][V];
// prim
int low[V], vis[V], P[V], G[V][V];
const int inf = ~0u>>2;
int prim(){
    for(int i=0;i<n;i++) vis[i] = 0, low[i] = inf, P[i] = -1;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            G[i][j] = 0;
    P[0] = low[0] = 0;
    int ans = 0;
    for(int i=0;i<n;i++){
        int s , mn = inf;
        for(int j= 0; j< n; j++) if(!vis[j] && low[j] < mn){
            mn = low[j]; s = j;
        }
        vis[s] = 1;
        ans += mn;
        if(P[s] != s) G[s][P[s]] = G[P[s]][s] = mn;
        for(int v = 0; v < n; v++) if(num[s][v])
            if(!vis[v] && low[v] > num[s][v] )
                low[v] = num[s][v], P[v] =s;
    }
    return ans;
}
// dfs
template <typename T> inline void chkmin(T &a, const T b){if(a>b)a=b;};
int pre[V],snd[V], tm, __ans[V][V];
typedef pair<intint > node;
priority_queue<node, vector<node> , greater <node> > Q[V];
int temp[V][V];
void dfs1(int u,int f){
    pre[u] = tm ++;
    for(int v = 0; v< n; v++) if(G[u][v] && pre[v] == -1)
        dfs1(v,u);
    snd[u] = tm ++;
}
#define ff first
#define ss second
void dfs(int u,int f) {
    while(!Q[u].empty()) Q[u].pop();
    for(int v=0;v<n;v++) if( G[u][v] && v!=f) {
        dfs(v,u);
        if(!Q[v].empty()) __ans[u][v] = __ans[v][u] = Q[v].top().ff;
        while(!Q[v].empty()) {
            int val = Q[v].top().ff;
            int to = Q[v].top().ss;
            chkmin(temp[u][to],val);
            Q[v].pop();
        }
    }
    for(int i=0;i<n;i++) if(i!=f){
        chkmin(temp[u][i],num[u][i]);
    }
    for(int v=0;v<n;v++) if(temp[u][v] != inf ) {
        if(pre[v] >= pre[u] && snd[v] <= snd[u]) continue;
        Q[u].push(make_pair(temp[u][v],v));
    }
}
void work(){
    tm = 0;
    for(int i=0;i<n;i++)
        pre[i] = -1;
    dfs1(0,0);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            temp[i][j] = __ans[i][j] = inf;
    dfs(0,0);
}
// main
int main(){
    while(~scanf("%d%d",&n,&m) && n) {
        int u,v,c;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) num[i][j] = inf;
        for(int i=0;i<m;i++) {
            scanf("%d%d%d",&u,&v,&c);
            num[u][v] = num[v][u] = c;
        }
        int t = prim();
        work();
        // query
        int q; double ans = 0;
        scanf("%d",&q);
        for(int oo=0;oo<q;oo++){
            scanf("%d%d%d",&u,&v,&c);
            if(!G[u][v])
                ans += t;
            else if(c <= __ans[u][v])
                ans += t - G[u][v] + c;
            else ans += t - G[u][v] + __ans[u][v];
        }
        printf("%.4lf\n", ans/q);
    }
    return 0;
}
posted on 2012-07-30 13:46 西月弦 阅读(397) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理