题意
给出一棵树，树边带有边权，问你能不能找出一条路径使得路径边权之和正好等于给出的k值。
思路
和这个题非常像，只不过题意从计算有多少点对之间距离小于k换成了判断有没有一条路径等于k。但实际上可以用一套思路解决。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXV = 100005; const int MAXE = 200005; const int INF = 0x3f3f3f3f; int nxt[MAXE],end[MAXE],head[MAXV],cost[MAXE],gtot,vis[MAXV]; int n; void init(){ gtot = 2; for(int i = 1; i<=n; i++){ head[i] = 0; } } void addEdge(int from,int to,int _cost){ end[gtot] = to; cost[gtot] = _cost; nxt[gtot] = head[from]; head[from] = gtot++; } int siz[MAXV],midpn,bal; void getbal(int cur,int par,int totsiz){ siz[cur] = 1; int dpn = 1; for(int j = head[cur]; j; j = nxt[j]){ int now = end[j]; if(now != par && !vis[now]){ getbal(now,cur,totsiz); siz[cur] += siz[now]; dpn = max(dpn,siz[now]); } } dpn = max(dpn,totsiz-siz[cur]); if(dpn < midpn){ midpn = dpn; bal = cur; } } int dis[MAXV],distot; void dfs_dis(int cur,int par,int hav = 0){ dis[distot++] = hav; siz[cur] = 1; for(int j = head[cur]; j; j = nxt[j]){ int now = end[j]; if(now != par && !vis[now]){ dfs_dis(now,cur,hav+cost[j]); siz[cur] += siz[now]; } } } int calc(int rt,int k){ int ret = 0; distot = 0; dfs_dis(rt,0); sort(dis,dis+distot); for(int i = 0; i < distot; i++){ pair<int*,int*> bin = equal_range(dis+i+1,dis+distot,k-dis[i]); ret += bin.second - bin.first; } return ret; } bool dfs_main(int cur,int k){ int cnt = 0; cnt += calc(cur,k); vis[cur] = true; for(int j = head[cur]; j; j = nxt[j]){ int now = end[j]; if(!vis[now]){ cnt -= calc(now,k-2*cost[j]); } } if(cnt > 0){ return true; }else{ for(int j = head[cur]; j; j = nxt[j]){ int now = end[j]; if(!vis[now]){ midpn = INF; getbal(now,cur,siz[now]); if(dfs_main(bal,k)){ return true; } } } } return false; } bool solve(int k){ for(int i = 1; i<= n; i++){ vis[i] = false; } midpn = INF; getbal(1,0,n); return dfs_main(bal,k); } int main(){ while(scanf(" %d",&n) != EOF && n){ init(); for(int i = 1; i <= n; i++){ int a,b; while(scanf(" %d",&a) != EOF && a){ scanf(" %d",&b); addEdge(i,a,b); addEdge(a,i,b); } } int q; while(scanf(" %d",&q) != EOF && q){ if(solve(q)){ puts("AYE"); }else{ puts("NAY"); } } puts("."); } } |
