HDU 4126 Genghis Khan the Conqueror MST+樹形dp

HDU 4126 Genghis Khan the Conqueror MST+樹形dp

題意：

給定n個點m條邊的無向圖。

下面m行給出邊和邊權

下面Q個詢問。

Q行每行給出一條邊（一定是m條邊中的一條）

表示修改邊權。

（數據保證修改後的邊權比原先的邊權大）

問：修改後的最小生成樹的權值是多少。

每個詢問互相獨立（即每次詢問都是對於原圖修改）

保證沒有重邊。

求：所有修改後的最小生成樹權值的平均值。

思路：

首先跑一個最小生成樹。

求得這個MST的權值 int mst;

對於每個詢問(u.v,dis);

若(u,v) 不是MST上的邊，則此時的權值就是 mst

否則我們斷開樹邊(u,v)，然後找u點集和v點集之間的邊中權值最小的邊cost[u][v];

這樣當前的權值就是 mst - g[u][v] + min(cost[u][v], dis);

剩下就是如何計算cost;

MST會求得一個無根樹。

我們把無根樹轉成以u為根時 ，對於v子樹其實是不變的。

剩下就是簡單dp了

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if(c=getchar(),c==EOF) return 0;
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
template 
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}
typedef long long ll;
using namespace std;
const ll inf = 100000000;
const int N = 3005;
ll g[N][N], d[N], mst, cost[N][N];
bool vis[N], choose[N][N];
int n, m;
vector G[N];
ll dfs(int u, int fa, int src){
    ll siz = inf;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(v == fa)continue;
        ll tmp = dfs(v, u, src);
        siz = min(siz, tmp);
        cost[u][v] = cost[v][u] = min(cost[u][v], tmp);
    }
    if(fa != src)
        siz = min(siz, g[u][src]);
    return siz;
}
int pre[N];
void MST(){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = g[i][j] = inf, choose[i][j] = 0;

    while(m--){
        int u, v; ll dis; rd(u);rd(v); rd(dis);
        g[u][v] = g[v][u] = min(g[u][v], dis);
    }
    for(int i = 0; i < n; i++)
    {
        d[i] = inf;
        G[i].clear();
        vis[i] = 0;
        pre[i] = -1;
    }
    d[0] = 0;
    mst = 0;
    for(int i = 0; i < n; i++)
    {
        int pos = -1;
        for(int j = 0; j < n; j++)
            if(!vis[j] &&(pos == -1 || d[pos] > d[j]))
                pos = j;
        if(pre[pos]!=-1)
        {
            G[pos].push_back(pre[pos]);
            G[pre[pos]].push_back(pos);
            choose[pos][pre[pos]] = choose[pre[pos]][pos] = 1;
        }
        for(int j = 0; j < n; j++)
            if(d[j] > g[j][pos])
            {
                d[j] = g[j][pos];
                pre[j] = pos;
            }
        vis[pos] = 1;
        mst += d[pos];
    }
}

int main() {
    int q, u, v; ll dis;
	while(cin>>n>>m, n+m) {
        MST();
        for(int i = 0; i < n; i++)
            dfs(i, -1, i);
        rd(q);
        ll ans = 0;
        for(int i = 1; i <= q; i++) {
            rd(u); rd(v); rd(dis);
            if(choose[u][v] == false)
                ans += mst;
            else
                ans += mst - g[u][v] + min(cost[u][v], dis);
        }
        printf("%.4f\n",(double)ans/(double)q);
	}
	return 0;
}