Spoj FTOUR Free Tour II

2019-11-08 02:59:20

字体：大中小

来源：转载

供稿：网友

传送门

http://www.spoj.com/PRoblems/FTOUR2/en/

题目大意

给出一棵树，其中每一节点都有一个颜色(黑色或白色)，每条边都有一个权值，现要求在树中找出一条链，使得链上的黑点数不超过给定的数k $k$ ，求权值和最大

我的想法

国家集训队论文： http://wenku.baidu.com/view/8861df38376baf1ffc4fada8.html 对链的操作可以想到用点分治。如果一条链不包括当前(根)节点的话，就递归好了如果包括根节点，那就把那条链从根节点劈开，剩下的两段一定在不同的子树中(如果这条链的一个端点就是根节点的话那就说另一段在某子树中长度为0)，这要也可以保证不会算出不合法的情况。然后我就这么劈开，提交，TLE 因为在递归子树的时候有讲究，令d(i) $d(i)$ 表示第i $i$ 棵子树中的包含最多黑色节点的链的黑色节点数，如果d(i)>k $d(i)>k$ ，令d(i)=k $d(i)=k$ ，因为如果一条链包含了多于k $k$ 个黑色节点的话肯定不合法，然后先从小的d(i) $d(i)$ 入手递归，在递归大的。再提交，WA 因为我忽略了根节点是黑色的情况继续提交，WA 因为k−d(i)−black(u) $k-d(i)-black(u)$ 在d(i)=k $d(i)=k$ 且u $u$ 是黑色节点的时候成了负数越错越勇，WA 因为在当两颗子树的黑点数加起来都小于k $k$ 的时候k−d(i)−black(u) $k-d(i)-black(u)$ 是没有意义的，于是我把它改成min(d(j),k−d(i)−black(u)) $min(d(j),k-d(i)-black(u))$ 第5次提交，WA 很多变量没有初始化，就比如说递归子树的时候d[] $d[]$ 没有清0，找重心的时候子树大小是错的.. 最后第8次才A

代码

#include <cstdio>#include <cstring>#include <algorithm>#define x first#define y second#define REP(i,_begin,_end) for(int i=(_begin);i!=(_end);++i)template<class T>T min(const T &a,const T &b){return a < b ? a : b;}template<class T>T max(const T &a,const T &b){return a > b ? a : b;}template<class T>bool chkmin(T &a,const T &b){return a > b ? a=b, 1 : 0;}template<class T>bool chkmax(T &a,const T &b){return a < b ? a=b, 1 : 0;}const int SN = 200000 + 50;const int Inf = 0x3f3f3f3f;int head[SN], nxt[SN<<1], to[SN<<1], wei[SN<<1], tot;int black[SN], size[SN], f[SN], g[SN], ans, sum, cnt, rt, n, m, k;std :: pair<int,int> deep[SN];bool vis[SN];void Read(int &);void Add(int, int, int);void GetRt(int, int);void GetG(int, int, int, int);void GetDeep(int, int, int, int);void GetSize(int, int);void Doit(int);int main(){ int x, y, z; Read(n), Read(k), Read(m); REP(i, 0, m) Read(x), black[x]=1; REP(i, 1, n) Read(x), Read(y), Read(z), Add(x, y, z); sum=n, cnt=Inf, GetRt(1,-1), Doit(rt); printf("%d/n",ans); return 0;}void Read(int &in){ char ch;int f=1; for(ch=getchar();ch>'9'||ch<'0';ch=getchar()) if(ch=='-') f=-1; for(in=0;ch>='0'&&ch<='9';ch=getchar()) in=in*10+ch-'0'; in *= f;}void Add(int u,int v,int w){ nxt[++tot]=head[u];head[u]=tot;to[tot]=v;wei[tot]=w; nxt[++tot]=head[v];head[v]=tot;to[tot]=u;wei[tot]=w;}void GetRt(int u,int fa){ int mx = 0; size[u] = 1; for(int i=head[u];i;i=nxt[i]) if(!vis[to[i]] && to[i]!=fa){ GetRt(to[i],u); size[u] += size[to[i]]; chkmax(mx,size[to[i]]); } if(chkmin(cnt,max(mx,sum-size[u]))) rt = u;}void GetG(int u,int fa,int t,int d){ if(t > k) return ; for(int i=head[u];i;i=nxt[i]) if(!vis[to[i]] && to[i]!=fa){ if(t+black[to[i]]<=k) chkmax(g[t+black[to[i]]],d+wei[i]); GetG(to[i], u, t+black[to[i]], d+wei[i]); }}void GetDeep(int u,int fa,int depth,int t){ if(depth > k) return; chkmax(deep[t].x, depth); for(int i=head[u];i;i=nxt[i]) if(!vis[to[i]] && to[i]!=fa) GetDeep(to[i],u,depth+black[to[i]],t);}void GetSize(int u,int fa){ size[u] = 1; for(int i=head[u];i;i=nxt[i]) if(!vis[to[i]] && to[i]!=fa) GetSize(to[i],u), size[u]+=size[to[i]];}void Doit(int u){ int t = 0; vis[u] = true; for(int i=head[u];i;i=nxt[i]) if(!vis[to[i]]) deep[t].x=0, GetDeep(to[i],u,black[to[i]],t), deep[t++].y=i; std :: sort(deep, deep+t); REP(i, 0, t) { chkmax(g[black[to[deep[i].y]]], wei[deep[i].y]); GetG(to[deep[i].y], u, black[to[deep[i].y]], wei[deep[i].y]); REP(j, 1, deep[i].x+1) chkmax(g[j], g[j-1]), chkmax(f[j], f[j-1]); REP(j, 0, deep[i].x+1) if(k-black[u]-j>=0) chkmax(ans, g[j]+f[min(deep[i].x,k-black[u]-j)]); REP(j, 0, deep[i].x+1) chkmax(f[j], g[j]), g[j] = 0; } REP(i, 0, deep[t-1].x+1) f[i] = 0; GetSize(u, -1); for(int i=head[u];i;i=nxt[i]) if(!vis[to[i]]) sum=size[to[i]], cnt=Inf, GetRt(to[i],u), Doit(rt);}

上一篇：c#的chart悬停选定数值操作

下一篇：BZOJ 3175: [Tjoi2013]攻击装置