bzoj 1912: [Apio2010]patrol 巡逻【不是dp是枚举+堆】

我是智障系列。用了及其麻烦的方法= =其实树形sp就能解决

设直径长度+1为len（环长）

首先k=1，直接连直径两端就好，答案是2*n-len

然后对于k=2，正常人的做法是树形dp：先求直径，然后把树的直径上的所有边权标为-1，再求一次直径设新直径+1为len2，答案是2*(n−1)−len−len2。

然后zz的做法是分两种情况：

len=n，直接输出n+1（因为要加个自环）

否则，答案可能从两种情况产生：

新选出的链两端在都原直径环某一个节点下面，这样的情况可以直接求这个节点子树的直径+1为mx，用2*n-len-mx+2（化简后）

或者要经过一段原直径dis，注意新加的边不算，用一个优先队列维护直径上第j个的最大深度mx，按mx+j排序，每次扫到一个点j，用2*n-len+3-(q.top().first+mx-j)更新答案即可

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int N=100005,inf=1e9;

int n,m,h[N],cnt,de[N],mx,s,t,fa[N],len,q[N],top,ans=inf,p[N];

bool v[N];

struct qwe

{

	int ne,to;

}e[N<<1];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

void dfs(int u,int fat,int len)

{

	fa[u]=fat;

	if(len>mx)

		mx=len,s=u;

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

		if(e[i].to!=fat&&!v[e[i].to])

			dfs(e[i].to,u,len+1);

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<n;i++)

	{

		int x=read(),y=read();

		add(x,y),add(y,x);

	}

	dfs(1,0,1);

	t=s;

	mx=0;

	dfs(s,0,1);

	len=mx;

	if(m==1)

	{

		printf("%d\n",2*n-len);

		return 0;

	}

	if(len==n)

	{

		printf("%d\n",n+1);

		return 0;

	}

	for(int x=s;x;x=fa[x])

		v[x]=1,q[++top]=x;//,cerr<<x<<" ";cerr<<endl;

	priority_queue<pair<int,int> >qq;

	for(int j=1;j<=top;j++)

	{

		mx=0;

		dfs(q[j],0,1);

		if(mx>1)

		{

			if(!qq.empty())

				ans=min(ans,2*n-len+3-(qq.top().first+mx-j));

			qq.push(make_pair(mx+j,j));

		}

	}

	for(int j=1;j<=top;j++)

	{

		mx=0;

		dfs(q[j],0,1);

		if(mx==1)

			continue;

		v[q[j]]=0;

		mx=0;//cerr<<q[j]<<" "<<s<<" ";

		dfs(s,0,1);//cerr<<mx<<endl;

		ans=min(ans,2*n-len-mx+2);

		v[q[j]]=1;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 1912: [Apio2010]patrol 巡逻【不是dp是枚举+堆】

最新文章

热门文章