題目描述：
求N<3,000個點(diǎn)的稠密圖的最小生成樹的每條邊的最佳替換邊。
算法分析：
先求最小生成樹，這個不用說了。
dp[i][j]表示，i和i的子孫到j(luò)的最小邊(不計算生成樹的邊)。
這個可以通過樹形DP(中序遍歷 + 后序遍歷)求的。
注意j不能是i的子孫，這個要通過時間戳來判斷。
同時用一個優(yōu)先級隊列，把這樣的邊都存起來。在回溯過程中僅用O(logE)的時間就可以判斷最佳邊了。
復(fù)雜度O(V*V*logE)
寫起來不太好寫，想到不難，但是復(fù)雜度不好把握。
#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<int, int > 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
西月弦 閱讀(418)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告