首页 > 代码库 > 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 <cstdio> #include <cstring> #include <string> #include <iostream> #include <queue> #include <algorithm> #include <cmath> template <class T> 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 <class T> 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<int> 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; }
HDU 4126 Genghis Khan the Conqueror MST+树形dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。