- 浏览: 381244 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (229)
- java编程 (4)
- java实用程序 (2)
- 算法设计 (34)
- 数据库 (8)
- ACM模板 (12)
- 技术术语 (1)
- java_web (3)
- php (22)
- eclipse (3)
- linux (25)
- linux命令使用心得 (3)
- web服务器 (8)
- IT知识 (2)
- 前端技术 (17)
- 开源软件 (5)
- vim (3)
- linux多线程 (9)
- web开发经验 (3)
- lua (5)
- linux编程 (3)
- smarty (1)
- mysql (4)
- Hive (2)
- 数据挖掘 (9)
- python (2)
- 生活 (1)
- C++ (2)
- 计算机 (1)
- objective-c (11)
- css (2)
- 游戏 (1)
- Mac (1)
最新评论
-
lr544463316:
我的怎么不行呀.....
Mysql Access denied for user ''@'localhost' to database 的一种解决方法 -
babaoqi:
使用时需要注意group_concat函数返回值的最大长度=g ...
mysql中的group_concat函数 -
代码能力弱成渣:
可以帮我看下我的代码么?我自己写的sam,也有ac过题的,但是 ...
求两个字符串的最长公共连续子序列(SAM实现) -
atgoingguoat:
有1000个?不过还是收藏下。
jquery常用的插件1000收集(转载)
突然发现剖分树可以在log(n)的时间里求出lca,于是又删了几十行的代码。
#include <iostream> #include <stdio.h> #include <vector> #include <algorithm> #include <ctime> using namespace std; const int N = 20005; const int M = 100005; const int QN = M; const int INF = 0X7FFFFFFF; typedef int vType; typedef pair<int, int> pii; #define mkpii make_pair<int, int> struct e{ int v; e* nxt; }es[N<<1], *fir[N]; struct node{ int ls, rs; //左右儿子的下标,为-1表示空 int l, r; //区间的左右标号 //数据域 int id; //如果这个是叶子节点,id表示代表原树中的节点的标号 vType Min; //Min为这一整段插入的一个最小值 int mid() { return (l + r) >> 1; } }nodes[N<<1]; struct se{ pii e; int len; }ses[M<<1], lea[M<<1]; int n, en, qn, m; vector<pii> qlca[N]; vector<se> nes[N]; int par[N], fa[N]; //par[i]为i的直接前驱, fa用于并查集; int ln, cnt; //ln为链的数目,cnt为剖分树中节点的数目 int leaNum; int sons[N], que[N], dep[N], id[N], st[N], ed[N], root[N], top[N], sNum[N]; //sons[i]表示i为根的子树的大小,dep[i]表示节点的i的深度,id[i]为i所在链的标号,st和ed记录每条链的左右标号,root记录每条链的根节点的下标 //top[i]为第i条链的顶部节点,sNum[i]表示i的直接后继的个数 int ith[N], pMin[N], seg[N]; //ith[i]表示节点i是其父节点的第ith[i]个儿子(按访问顺序), //seg在链上构建线段树的时候使用 vType iw[N]; //iw[i]表示节点i在最小生成树中与其他节点之间的边的权值的总和 int tr; //最小生成树的根节点 inline void add_e(int u, int v){ es[en].v = v; es[en].nxt = fir[u]; fir[u] = &es[en++]; } inline void newNode(int& id, int l, int r){ nodes[cnt].ls = nodes[cnt].rs = -1; nodes[cnt].l = l; nodes[cnt].r = r; nodes[cnt].Min = INF; id = cnt++; } void build(int& id, int l, int r){ //在剖分出来的链上构建线段树 newNode(id, l, r); if(l >= r){ nodes[id].id = seg[l]; return ; } int mid = (l+r)>>1; build(nodes[id].ls, l, mid); build(nodes[id].rs, mid+1, r); } void initTree(){ //初始化剖分树 //确定父亲 int l, r, u, v, i; e* cur; l = r = 0; que[r++] = tr; par[tr] = -1; dep[tr] = 0; while(l != r){ u = que[l++]; int g = 1; for(cur = fir[u]; cur; cur = cur->nxt){ if((v = cur->v) != par[u]){ que[r++] = v; par[v] = u; dep[v] = dep[u]+1; ith[v] = g++; } } } //计算子树大小 for(i = 1; i <= n; i++){ sons[i] = 1; sNum[i] = 0; id[i] = -1; } for(i = r-1; i >= 0; i--){ u = que[i]; if(par[u] >= 0){ sons[par[u]] += sons[u]; sNum[par[u]]++; } } //剖分链 l = r = 0; que[r++] = tr; ln = cnt = 0; while(l != r){ u = que[l++]; st[ln] = dep[u]; //用节点的深度作为线段树中区间的左右标号 top[ln] = u; while(u >= 0){ id[u] = ln; ed[ln] = dep[u]; seg[dep[u]] = u; int best; for(cur = fir[u], best=-1; cur; cur = cur->nxt){ if(id[v = cur->v] == -1){ if(best == -1 || (best >= 0 && sons[v] > sons[best])){ best = v; } } } if(best >= 0){ for(cur = fir[u]; cur; cur = cur->nxt){ if(id[v = cur->v] == -1 && best != v){ que[r++] = v; } } } u = best; } root[ln] = -1; build(root[ln], st[ln], ed[ln]); ln++; } } int qrylKthFar(int& id, int i, int k){ //在链上查询i的第k个父节点(第0个为自己) if(nodes[id].l == nodes[id].r) return nodes[id].id; int mid = nodes[id].mid(); if(i - mid - 1 >= k) return qrylKthFar(nodes[id].rs, i, k); else return qrylKthFar(nodes[id].ls, i, k); } int qryKthFar(int i, int k){ //查询i的第k个父节点(第0个为自己) int u = i, ri; while(true){ ri = id[u]; if(dep[u] - st[ri] >= k){ return qrylKthFar(root[ri], dep[u], k); }else{ k -= dep[u] - st[ri] + 1; u = par[top[ri]]; } } } void inslMin(int& id, int ql, int qr, int mv){ if(id == -1) return ; if(ql <= nodes[id].l && nodes[id].r <= qr){ if(nodes[id].Min > mv){ nodes[id].Min = mv; } return; } if(nodes[id].l == nodes[id].r) return; int mid = nodes[id].mid(); if(ql <= mid){ inslMin(nodes[id].ls, ql, qr, mv); } if(qr > mid){ inslMin(nodes[id].rs, ql, qr, mv); } } void insMin(int i, int k, vType mv){ //在节点i和i的第k个父节点之间插入mv int b, u; u = i; while(true){ b = id[u]; if(dep[u]-st[b] >= k){ inslMin(root[b], dep[u]-k, dep[u], mv); return; }else{ inslMin(root[b], st[b], dep[u], mv); k -= dep[u] - st[b] + 1; u = par[top[b]]; } } } bool input(){ scanf("%d%d", &n, &m); int i, k, tn; for(i = tn = 0; i < m; i++){ scanf("%d%d%d%d", &ses[i].e.first, &ses[i].e.second, &ses[i].len, &k); if(k == 1){ //既然这条边还在使用,可以把它的边权设为0 ses[i].len = 0; } if(ses[i].e.first != ses[i].e.second){ tn++; } } m = tn; return true; } inline bool cmp(se a, se b){ return a.len < b.len; } int findFa(int u){ int k = u; while(k != fa[k]) k = fa[k]; while(u != k){ int tf = fa[u]; fa[u] = k; u = tf; } return k; } void merge(int u, int v){ int fu, fv; fu = findFa(u); fv = findFa(v); fa[fu] = fv; } int kruskal(int n, int m, int& leaNum, bool flag){ //flag为true表示需要构图 int i, ans, k, u, v; for(i = 1; i <= n; i++){ fa[i] = i; } if(flag){ for(i = 1; i <= n; i++){ iw[i] = 0; fir[i] = NULL; } en = leaNum = 0; } sort(ses, ses + m, cmp); for(i = ans = 0, k = 1; k < n && i < m; i++){ u = ses[i].e.first; v = ses[i].e.second; if(findFa(u) != findFa(v)){ ans += ses[i].len; k++; merge(u, v); if(flag){ add_e(u, v); add_e(v, u); iw[u] += ses[i].len; iw[v] += ses[i].len; } }else if(flag){ //这条边被剩出来 lea[leaNum++] = ses[i]; } } if (flag) { for (; i < m; i++) { lea[leaNum++] = ses[i]; } } if(k < n) ans = INF; return ans; } void handlelca(int u, int v, int anc, int len){ if(u != anc && v != anc){ int ku, kv; ku = qryKthFar(u, dep[u] - dep[anc] - 1); kv = qryKthFar(v, dep[v] - dep[anc] - 1); se te; te.e.first = ith[ku]; te.e.second = ith[kv]; te.len = len; nes[anc].push_back(te); } if(dep[anc] + 2 <= dep[u]){ insMin(u, dep[u] - dep[anc] - 2, len); } if(dep[anc] + 2 <= dep[v]){ insMin(v, dep[v] - dep[anc] - 2, len); } } //qn为查询lca的次数,qs记录查询lca的两个几点,anc记录每次查询的结果 int getlca(int u, int v){ while(id[u] != id[v]){ if(id[u] < id[v]) swap(u, v); u = par[top[id[u]]]; } if(dep[u] < dep[v]) swap(u, v); return v; } void lca(se* qs, int qn){ int i; for(i = 1; i <= n; i++){ nes[i].clear(); } for(i = 0; i < qn; i++){ int u, v, anc; u = qs[i].e.first; v = qs[i].e.second; anc = getlca(u, v); handlelca(v, u, anc, qs[i].len); } } void getpMin(int& id, int mv){ if(mv > nodes[id].Min){ mv = nodes[id].Min; } if(nodes[id].l == nodes[id].r){ pMin[nodes[id].id] = mv; return; } getpMin(nodes[id].ls, mv); getpMin(nodes[id].rs, mv); } void getpMin(){ int i; for(i = 0; i < ln; i++){ getpMin(root[i], INF); } } void solve(){ tr = 1; //设置根节点 int sum, i, sn, v, num; e* cur; sum = kruskal(n, m, leaNum, true); initTree(); lca(lea, leaNum); getpMin(); for(i = 1; i <= n; i++){ num = 0; sn = sNum[i]; if (par[i] >= 1) { sn++; for (cur = fir[i]; cur; cur = cur->nxt) { if ((v = cur->v) != par[i] && pMin[v] < INF) { ses[num].e.first = sn; ses[num].e.second = ith[v]; ses[num].len = pMin[v]; num++; } } } int size = nes[i].size(), j; for(j = 0; j < size; j++){ ses[num++] = nes[i][j]; } int ans = kruskal(sn, num, leaNum, false); if(ans < INF){ ans += sum - iw[i]; printf("%d\n", ans); }else{ printf("inf\n"); } } } int main() { int t; scanf("%d", &t); while(t--){ input(); solve(); } return 0; }
发表评论
-
升序数组中求一个key出现的次数
2013-01-09 23:08 1072算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需 ... -
判断单链表是否有环
2013-01-08 19:07 892算法思路: 指针p1和p2的起始值均为链表的表头,指针p1每次 ... -
hdu3684
2011-11-15 20:11 900/* 刚开始打了个记录上下左右四个点的,一直tle。 ... -
hdu3686
2011-11-14 20:43 1011/* 无向图边的双连通分量,在同一个连通分量里的边之间 ... -
poj3968
2011-11-14 04:45 1385source: http://poj.org/problem ... -
uva2819
2011-11-13 02:20 867source: http://livearchive.onli ... -
manacher算法
2011-11-11 00:06 2413const int LEN=110005; const ... -
hdu4118
2011-11-09 21:53 1167枚举每条边最多被经过的次数即可 #include ... -
hdu4115
2011-11-09 16:27 1004source: http://acm.hdu.edu.cn/ ... -
uva(Transitive Closure)
2011-11-08 14:45 889source: http://livearchive.onli ... -
zoj3500
2011-11-07 17:41 930求两个球的体积交或者并 #include <cs ... -
zoj3545
2011-11-04 18:18 846/* AC自动机 相当暴力的 解法: mark[i ... -
zoj3190
2011-11-04 17:34 1262/* * AC自动机,先对资源串和病毒串构成的字符串 ... -
zoj3228
2011-11-04 16:12 930/* * AC自动机,每个节点 添加一个d表示节点代 ... -
poj3691(DNA Repair)
2011-11-04 13:18 1456/* AC自动机,增设虚拟节点,求长度为n的字符串中包 ... -
hdu2825
2011-11-04 11:53 963/* AC自动机,增设虚拟节点,求长度为n的字符 ... -
hdu4095
2011-11-03 13:19 993/* 第一步,构建BST,用第一个数作为bst的 ... -
zoj3540
2011-11-02 21:33 897/* 其实就是把总共的 放置次数减去不能放置的那些就行 ... -
poj1741(树的分治,基于边的 分治)
2011-11-02 20:25 3329/* 树基于边的分治算法,计算树中距离小于等于k的点 ... -
hdu2939
2011-10-29 18:36 830source: http://acm.hdu.edu.cn/s ...
相关推荐
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
NULL 博文链接:https://128kj.iteye.com/blog/1734821
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
杭电ACM课件2014版之 (HDUACM201403版_08)计算几何基础
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
hdu计算理论复习资料
HDU最全ac代码