题解 P1453 【城市环路】

P1453 城市环路

感觉基环树（or环套树）的题目一般都是找到树上的环，断掉一条边再进行树上的操作（如noip2018P5022 旅行）

双倍经验：P2607 [ZJOI2008]骑士

P1453和P2607这两题实际上就是基环树上的P1352 没有上司的舞会，用树形DP即可，但是因为有环，所以要先找到环再删一条边才能DP

至于树形DP就不多说了，毕竟是基环树，最主要的就是找环操作了，翻了翻题解，大概有下面几种方法：

一. 读入时判断

并查集，若两点在一个并查集中则记录下来，不连边不合并
（不建议使用）bool记录点是否出现过，若读入时两点在之前都已出现了，则为环，不连边（BUG：本题数据较弱可过，但可能在一些数据中出错，看评论中有一组hack数据：5 1 2 3 4 5 0 1 2 3 2 4 0 2 3 4 9.0，答案为63.0，但这种找环方法会超时）

二、读入后判断

如本程序，dfs找环，找到时记录两点a,b或边编号e，dp时不仅要判断v!=fa，还应判断(u!=a || v!=b) && (u!=b || v!=a)或(e!=i && (e^1)!=i)(双向边)
（不建议使用）连单向边u->v（注意要保证有有向环），记录fa[v]=u，从一个已存在的点开始不断找fa直到遇到走过的则找到了环。这种写法可以用在P2607（见这个题解），此题未必可行

while(!vis[fa[rt]]) rt=fa[rt],vis[rt]=1;//rt与fa[rt]连为了环

对于此题，找到环上两点a，b后，分别以a，b为根做两次树形DP，第一次取f[a][0]，第二次取f[b][0]（这样保证a与b虽相邻但不会同时被被取），取max(f[a][0],f[b][0])与K相乘即可

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

#define ll int //这个代码是在P2607的基础上修改的，所以直接把ll定义为int了

const int N=1e5+100;

int h[N],rt,rt2,n,cnt,val[N];

bool vis[N];

ll f[N][2],ans;

struct edge {

	int v,h;

} e[N<<1];

inline void add(int u,int v) {

	e[++cnt]=(edge) {

		v,h[u]

	},h[u]=cnt;

}

void dp(int x,int fa) {

	vis[x]=1,f[x][1]=val[x];

	for (int i=h[x],v; i; i=e[i].h) {

		v=e[i].v;

		if ((x!=rt || v!=rt2) && (x!=rt2 || v!=rt) && v!=fa)

			dp(v,x),

			f[x][0]+=max(f[v][0],f[v][1]),

			         f[x][1]+=f[v][0];

	}

}

bool find(int x,int fa) {  //dfs找环

	vis[x]=1;

	for(int i=h[x]; i; i=e[i].h)

		if (e[i].v^fa)

			if (vis[e[i].v]) {

				rt=e[i].v,rt2=x; //找到了环，记录起端点（相当于切断i这条边）

				return 1;

			} else if (find(e[i].v,x)) return 1;

}

void solve(int x) { //分别以两端点做树形DP

	find(x,-1);

	dp(rt,rt);

	ll tmp=f[rt][0];

	memset(f,0,sizeof f);

	dp(rt2,rt2);

	ans=max(tmp,f[rt2][0]);

}

int main() {

	scanf("%d",&n);

	for (int i=0; i<n; i++) scanf("%d",&val[i]);

	for (int i=1,x,y; i<=n; i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);

	solve(0); //注意若是森林需枚举1~n的点

	double tmp;

	scanf("%lf",&tmp);

	printf("%.1lf",(double)ans*tmp);

}

巴特西

题解 P1453 【城市环路】

双倍经验：P2607 [ZJOI2008]骑士

最新文章

热门文章