首页 > 代码库 > hdu5016
hdu5016
题意：给定一个n个点的图，这个图是一棵树，然后有些点建立了集市。并且没有集市的地方去集市一定是去最近的，如果距离相同，那么则去标号最小的。。现在你还能在建一个集市，问建完这个集市最多有多少个点来这里。。
思路：
现对于每个点求该点到有标记点最近的距离，记录距离及其最近标号，可以用树形dp或者spfa搞。。
然后我们任意选定一个点建树，建完后进行点分治。。
对于当前分治快的跟rt，求rt到每个点的距离为dis，near为到标记点最近的距离
那么对于不同子树的点u,v,如果dis[u] + dis[v] < near[v]，那么如果u建立集市v肯定到u。。
那么我们把式子变形下，dis[u] < near[v] - dis[v],对于u直接二分查找统计即可。。
我们可以先不管哪棵子树先统计一边，然后再减去相同的即可，这样写起来方便点。。写起来还蛮像poj1741的。。
code：
1 /* 2 * Author: Yzcstc 3 * Created Time: 2014/10/2 17:37:34 4 * File Name: hdu5016.cpp 5 */ 6 #pragma comment(linker, "/STACK:102400000,102400000") 7 #include<cstdio> 8 #include<iostream> 9 #include<cstring> 10 #include<cstdlib> 11 #include<cmath> 12 #include<algorithm> 13 #include<string> 14 #include<map> 15 #include<set> 16 #include<vector> 17 #include<queue> 18 #include<stack> 19 #include<ctime> 20 #define repf(i, a, b) for (int i = (a); i <= (b); ++i) 21 #define repd(i, a, b) for (int i = (a); i >= (b); --i) 22 #define M0(x) memset(x, 0, sizeof(x)) 23 #define clr(x, y) memset(x, y, sizeof(x)) 24 #define N 120000 25 #define Inf 0x3fffffff 26 #define x first 27 #define y second 28 using namespace std; 29 typedef pair<int, int> pii; 30 struct edge{ 31 int v, w, next; 32 edge(){} 33 edge(int _v, int _w, int _next):v(_v), w(_w), next(_next){} 34 } e[N<<1]; 35 int last[N], n, len, have[N], ans[N]; 36 int inq[N]; 37 pii ner[N]; 38 39 void add(int u, int v, int w){ 40 e[len] = edge(v, w, last[u]), last[u] = len++; 41 } 42 43 void init(){ 44 clr(last, -1); 45 len = 0; 46 int u, v, w; 47 for (int i = 1; i < n; ++i){ 48 scanf("%d%d%d", &u, &v, &w); 49 add(u, v, w), add(v, u, w); 50 } 51 repf(i, 1, n) scanf("%d", &have[i]); 52 } 53 54 void gao(){ 55 repf(i, 0, n) ner[i].x = ner[i].y = Inf, inq[i] = 0; 56 queue<int> q; 57 repf(i, 1, n) if (have[i]){ 58 ner[i].x = 0, ner[i].y = i; 59 q.push(i), inq[i] = 1; 60 } 61 int u, v; 62 pii tmp; 63 while (!q.empty()){ 64 u = q.front(); 65 q.pop(), inq[u] = 0; 66 for (int p = last[u]; ~p; p = e[p].next){ 67 v = e[p].v; 68 tmp.x = ner[u].x + e[p].w, tmp.y = ner[u].y; 69 if (tmp < ner[v]){ 70 ner[v] = tmp; 71 if (!inq[v]) inq[v] = 1, q.push(v); 72 } 73 } 74 } 75 76 } 77 /*** 点分治-begin **/ 78 int vis[N], sz, msize[N], f[N], size[N], belong[N], ss, ff[N]; 79 int dis[N]; 80 pair<int, int> s[N], tp; 81 82 void dfs(int u, int fa){ //calculate the size 83 f[sz++] = u; 84 msize[u] = 0, size[u] = 1; 85 int v; 86 for (int p = last[u]; ~p; p = e[p].next){ 87 v = e[p].v; 88 if (v == fa || vis[v]) continue; 89 dfs(v, u); 90 size[u] += size[v]; 91 msize[u] = max(size[v], msize[u]); 92 } 93 } 94 95 void dfs(int u, int fa, int dist){ 96 dis[u] = dist, ff[ss++] = u; 97 int v; 98 for (int p = last[u]; ~p; p = e[p].next){ 99 v = e[p].v;100 if (v == fa || vis[v]) continue;101 dfs(v, u, dist + e[p].w);102 } 103 }104 105 void calculate(int u, int dist){106 ss = 0;107 dfs(u, 0, dist);108 for (int i = 0; i < ss; ++i)109 s[i].x = ner[ff[i]].x - dis[ff[i]], s[i].y = ner[ff[i]].y;110 sort(s, s+ss);111 int t;112 for (int i = 0; i < ss; ++i) if (!have[ff[i]]){113 tp.x = dis[ff[i]], tp.y = ff[i];114 t = lower_bound(s, s+ss, tp) - s;115 ans[ff[i]] += (dist > 0) ? (t - ss) : (ss - t); 116 } 117 }118 119 void dfs(int u){120 sz = 0;121 dfs(u, 0);122 int rt = 0, tmp, v;123 for (int i = 0; i < sz; ++i){124 tmp = max(msize[f[i]], sz-1-size[f[i]]);125 if (tmp <= (sz>>1)) { rt = f[i]; break; }126 }127 calculate(rt, 0);128 vis[rt] = 1;129 for (int p = last[rt]; ~p; p = e[p].next){130 v = e[p].v;131 if (vis[v]) continue;132 calculate(v, e[p].w);133 dfs(v);134 }135 }136 /**** 点分治-end***/137 138 void solve(){139 gao();140 M0(vis);141 M0(ans);142 dfs(1);143 int mx = 0;144 for (int i = 1; i <= n; ++i)145 mx = max(ans[i], mx);146 printf("%d\n", mx); 147 }148 149 int main(){150 // freopen("a.in", "r", stdin);151 // freopen("a.out", "w", stdout);152 while (scanf("%d", &n) != EOF){153 init();154 solve();155 }156 return 0;157 }
hdu5016
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。