首页 > 代码库 > HDU 4126 POJ 4006 Genghis Khan the Conqueror
HDU 4126 POJ 4006 Genghis Khan the Conqueror
题意:
n(3000)个点的图 q(10^4)次操作 每次操作从原图更改一条边的权值 问q次操作后最小生成树的平均值是多少
思路:
先求最小生成树 然后讨论 如果更改的不是树边 则最小生成树不变 如果是树边 就要选择原图中的非树边和更改后的这条边其中较小的一个形成新树
难做的只有“是树边”这种情况 我们考虑 原图中的非树边与原树一定可以形成一个环 那么我们可以这样理解 只要断掉的边是环内的树边 那么都可以用这条非树边补上形成新树 也就是说 这条非树边覆盖了环内树边形成的路径!!
因此我们可以对树进行边剖分 利用线段树 达到非树边"区间覆盖"的操作 然后对于每次询问 从断开的两个点查询最小值 与更改后的边比较即可
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<ctime> #include<cmath> using namespace std; typedef long long LL; #define N 3010 #define Q 10010 #define L(x) (x<<1) #define R(x) ((x<<1)|1) #define MID(x,y) ((x+y)>>1) #define inf 2147483647 inline bool scand(int &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; } int n, m, q; LL minCostTree, ans; struct edge { int v, w, next; } ed[N << 1]; int head[N], tot; void add(int u, int v, int w) { ed[tot].v = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot++; } int dep[N], pre[N], size[N], hson[N]; void dfs1(int u, int fa) { dep[u] = dep[fa] + 1; pre[u] = fa; size[u] = 1; for (int i = head[u]; ~i; i = ed[i].next) { int v = ed[i].v; if (v != fa) { dfs1(v, u); size[u] += size[v]; if (size[v] > size[hson[u]]) hson[u] = v; } } } int top[N], tid[N], idx; void dfs2(int u, int tp) { top[u] = tp; tid[u] = idx; idx++; if (hson[u]) dfs2(hson[u], tp); for (int i = head[u]; ~i; i = ed[i].next) { int v = ed[i].v; if (v != hson[u] && v != pre[u]) dfs2(v, v); } } struct node { int l, r, w, lazy; } f[N << 2]; void down(int i) { if (f[i].lazy != inf) { f[L(i)].w = min(f[L(i)].w, f[i].lazy); f[L(i)].lazy = min(f[L(i)].lazy, f[i].lazy); f[R(i)].lazy = min(f[R(i)].lazy, f[i].lazy); f[R(i)].w = min(f[R(i)].w, f[i].lazy); f[i].lazy = inf; } } void up(int i) { f[i].w = min(f[L(i)].w, f[R(i)].w); } void init(int l, int r, int i) { // cout << l << " " << r << endl; f[i].l = l; f[i].r = r; f[i].w = f[i].lazy = inf; if (l == r) return; int mid = MID(l,r); init(l, mid, L(i)); init(mid + 1, r, R(i)); } void update(int l, int r, int i, int key) { // cout << l << " -> " << r << " " << i << " [ " << f[i].l << " , " << f[i].r // << " ]" << endl; if (l == f[i].l && r == f[i].r) { f[i].w = min(f[i].w, key); f[i].lazy = min(f[i].lazy, key); return; } down(i); int mid = MID(f[i].l,f[i].r); if (r <= mid) update(l, r, L(i), key); else if (l > mid) update(l, r, R(i), key); else { update(l, mid, L(i), key); update(mid + 1, r, R(i), key); } up(i); } int query(int l, int r, int i) { if (l == f[i].l && r == f[i].r) return f[i].w; down(i); int mid = MID(f[i].l,f[i].r); int res; if (r <= mid) res = query(l, r, L(i)); else if (l > mid) res = query(l, r, R(i)); else { res = query(l, mid, L(i)); res = min(res, query(mid + 1, r, R(i))); } up(i); return res; } void Cover(int u, int v, int w) { int fu = top[u], fv = top[v]; while (fu != fv) { if (dep[fu] < dep[fv]) { swap(fu, fv); swap(u, v); } // cout << tid[fu] << " to " << tid[u] << endl; update(tid[fu], tid[u], 1, w); u = pre[fu]; fu = top[u]; } if (u == v) return; if (dep[u] > dep[v]) swap(u, v); // cout << tid[u] + 1 << " *to* " << tid[v] << endl; update(tid[u] + 1, tid[v], 1, w); } int Query(int u, int v) { int res = inf; int fu = top[u], fv = top[v]; while (fu != fv) { if (dep[fu] < dep[fv]) { swap(fu, fv); swap(u, v); } res = min(res, query(tid[fu], tid[u], 1)); u = pre[fu]; fu = top[u]; } if (u == v) return res; if (dep[u] > dep[v]) swap(u, v); res = min(res, query(tid[u] + 1, tid[v], 1)); return res; } int fa[N]; int getf(int x) { if (x != fa[x]) fa[x] = getf(fa[x]); return fa[x]; } struct edgerank { int u, v, w, used; bool operator<(const edgerank fa) const { return w < fa.w; } } edr[N * N]; struct question { int u, v, w; bool operator<(const question ff) const { return w < ff.w; } } ask[Q]; int main() { for (;;) { scand(n); scand(m); if (!n && !m) break; for (int i = 0; i < m; i++) { scand(edr[i].u); scand(edr[i].v); scand(edr[i].w); edr[i].u++; edr[i].v++; edr[i].used = 0; } //clear for (int i = 1; i <= n; i++) { fa[i] = i; head[i] = -1; } tot = 0; minCostTree = 0; //minCostTree sort(edr, edr + m); for (int i = 0, cnt = 0; i < m; i++) { int fu = getf(edr[i].u), fv = getf(edr[i].v); if (fu != fv) { fa[fv] = fu; cnt++; minCostTree += edr[i].w; add(edr[i].u, edr[i].v, edr[i].w); add(edr[i].v, edr[i].u, edr[i].w); edr[i].used = 1; if (cnt == n - 1) break; } } //clear idx = 1; for (int i = 1; i <= n; i++) hson[i] = 0; //heavyLight dfs1(1, 0); dfs2(1, 1); //input ask scand(q); for (int i = 0; i < q; i++) { scand(ask[i].u); scand(ask[i].v); scand(ask[i].w); ask[i].u++; ask[i].v++; } //solve int ide = 0; ans = 0; init(1, n, 1); sort(ask, ask + q); for (int i = 0; i < q; i++) { if (ask[i].u == ask[i].v) { ans += minCostTree; continue; } int intree = 0, treeedge; for (int j = head[ask[i].u]; ~j; j = ed[j].next) { if (ed[j].v == ask[i].v) { intree = 1; treeedge = ed[j].w; break; } } if (intree) { while (ide < m && ask[i].w > edr[ide].w) { if (!edr[ide].used) { // cout << ide << endl; Cover(edr[ide].u, edr[ide].v, edr[ide].w); // cout << ide << endl; } ide++; } // cout << i << " can update" << endl; int best = Query(ask[i].u, ask[i].v); ans += minCostTree - treeedge + min(best, ask[i].w); // cout << i << " can query" << endl; } else { ans += minCostTree; } // cout << i << " normal" << endl; } //output printf("%.4f\n", (double) (ans) / q); } return 0; }
HDU 4126 POJ 4006 Genghis Khan the Conqueror
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。