• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            算法學社
            記錄難忘的征途
            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 西月弦 閱讀(413) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            久久播电影网| 久久777国产线看观看精品| 久久久久久久久久久免费精品| 国产国产成人精品久久| 国产精品久久久久久久久免费| 国产午夜精品久久久久九九电影 | 国产毛片久久久久久国产毛片| 99久久精品国产综合一区| 久久精品国产欧美日韩| 99久久免费国产精品特黄| 精品国产一区二区三区久久| 久久久精品人妻无码专区不卡| 国内精品久久久久影院薰衣草 | 无码国内精品久久人妻| 日本精品久久久久中文字幕| 一本久久a久久精品综合香蕉| 国产精品久久久久AV福利动漫| 国内精品久久久久久久影视麻豆| 亚洲综合熟女久久久30p| 亚洲欧美日韩精品久久| 久久久久亚洲AV无码专区体验| 久久久久国产精品三级网| 国产成人精品久久一区二区三区| 手机看片久久高清国产日韩| 狠狠色伊人久久精品综合网 | 久久综合久久自在自线精品自| 久久精品无码av| 久久国产成人精品麻豆| 久久久国产精品亚洲一区| 一级做a爰片久久毛片毛片| 国产三级观看久久| 日本精品久久久中文字幕| 久久久久亚洲AV无码永不| 日韩精品久久久肉伦网站| 欧美日韩精品久久久免费观看| 热RE99久久精品国产66热| 精品久久人人做人人爽综合 | 久久SE精品一区二区| 武侠古典久久婷婷狼人伊人| 久久se这里只有精品| 国产激情久久久久影院小草|