YZOJ P3924 [IOI2011]Race

时间限制：2000MS 内存限制：131072KB

难度： $7.0$

题目描述

给一棵树，每条边有权。

求一条简单路径，权值和等于 $K$ ，且经过边的数量最小。

$N \leq 200000, K \leq 1000000$ 。

输入格式

第一行两个整数 $n$ ， $k$ 。

第 $2$ ~ $n$ 行每行三个整数，表示一条无向边的两端和权值（注意点的编号从 $0$ 开始）。

输出格式

一个整数，表示最小边数量。

如果不存在这样的路径，输出 $-1$ 。

样例输入

4 3

0 1 1

1 2 2

1 3 4

样例输出

2

Source: BZOJ 2599

因为本题 $K$ 较小，所以可能会有其他做法。

记 $ans_i$ 为满足条件（权值和为 $K$ ），并且经过边数为 $i$ 的点对的个数。

正贡献就是 $+1$ ，消去重复答案就是 $-1$ 。

然后就是一个裸的点分治。

使用双指针时注意有 $0$ 边权！！！

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>

#define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_))

#ifdef ONLINE_JUDGE
	char __B[1<<15],*__S=__B,*__T=__B;
	#define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++)
#endif
inline int getnum()
{
	register char c=0;
	while(!(c>='0' && c<='9'))
		c=getchar();
	register int a=0;
	while(c>='0' && c<='9')
		a=a*10+c-'0',c=getchar();
	return a;
}

int gcnt,ghead[205050],gnext[2050505],gnode[2050505],gval[2050505];
inline void insertLine(register int s,register int t,const int&val)
{
	gnext[++gcnt]=ghead[s],ghead[s]=gcnt,gnode[gcnt]=t,gval[gcnt]=val;
	gnext[++gcnt]=ghead[t],ghead[t]=gcnt,gnode[gcnt]=s,gval[gcnt]=val;
}

int K;
int root,mxsroot,asize,size[205050];
bool vis[205050];
void DFS_GetRoot(register int o,register int f)
{
	size[o]=1;
	register int mxs=0;
	for(register int j=ghead[o],t;j;j=gnext[j])
		if((t=gnode[j])!=f && !vis[t])
		{
			DFS_GetRoot(t,o);
			size[o]+=size[t];
			mxs=_max(mxs,size[t]);
		}
	mxs=_max(mxs,asize-size[o]);
	if(!root || mxs<mxsroot)
		mxsroot=mxs,root=o;
}

int depth[205050],dist[205050],llst,lst[205050];
void DFS_GetDepth(register int o,register int f)
{
	lst[++llst]=o;
	for(register int j=ghead[o],t;j;j=gnext[j])
		if((t=gnode[j])!=f && !vis[t])
		{
			depth[t]=depth[o]+gval[j],dist[t]=dist[o]+1;
			DFS_GetDepth(t,o);
		}
}

struct _comp
{
	bool operator () (const int&a,const int&b)
	{
		return depth[a]<depth[b];
	}
};

int ans[205050];
inline void CalcAns(register int o,register int diff=0,register int delta=1)
{
	depth[o]=diff,dist[o]=(delta<0);
	llst=0,DFS_GetDepth(o,0);
	std::sort(&lst[1],&lst[llst+1],_comp());
	register int l=1,r=llst;
	while(l<r)
	{
		while(l<r && depth[lst[l]]+depth[lst[r]] > K)
			r--;
		for(register int j=r;depth[lst[l]]+depth[lst[j]]==K && j>l;j--)
			ans[dist[lst[l]]+dist[lst[j]]]+=delta;
		l++;
	}
}

void DFS(register int o)
{
	CalcAns(o);
	vis[o]=true;
	for(register int j=ghead[o],t;j;j=gnext[j])
		if(!vis[t=gnode[j]])
		{
			CalcAns(t,gval[j],-1);
			asize=size[t],root=mxsroot=0,DFS_GetRoot(t,0);
			DFS(root);
		}
}

int main()
{
	register int N=getnum(),K=getnum();
	::K=K;
	for(register int i=1;i<=N-1;i++)
	{
		register int a=getnum()+1,b=getnum()+1,v=getnum();
		insertLine(a,b,v);
	}
	
	asize=N,root=mxsroot=0,DFS_GetRoot(1,0);
	DFS(root);
	for(register int i=1;i<=N;i++)
		if(ans[i])
		{
			printf("%d\n",i);
			return 0;
		}
	printf("%d\n",-1);
	
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <climits>

#include <algorithm>

#define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_))

#ifdef ONLINE_JUDGE

char __B[1<<15],*__S=__B,*__T=__B;

#define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++)

#endif

inline int getnum()

{

while(!(c>='0' && c<='9'))

c=getchar();

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

a=a*10+c-'0',c=getchar();

return a;

}

int gcnt,ghead[205050],gnext[2050505],gnode[2050505],gval[2050505];

inline void insertLine(register int s,register int t,const int&val)

{

gnext[++gcnt]=ghead[s],ghead[s]=gcnt,gnode[gcnt]=t,gval[gcnt]=val;

gnext[++gcnt]=ghead[t],ghead[t]=gcnt,gnode[gcnt]=s,gval[gcnt]=val;

}

int K;

int root,mxsroot,asize,size[205050];

bool vis[205050];

void DFS_GetRoot(register int o,register int f)

{

size[o]=1;

for(register int j=ghead[o],t;j;j=gnext[j])

if((t=gnode[j])!=f && !vis[t])

{

DFS_GetRoot(t,o);

size[o]+=size[t];

mxs=_max(mxs,size[t]);

}

mxs=_max(mxs,asize-size[o]);

if(!root || mxs<mxsroot)

mxsroot=mxs,root=o;

}

int depth[205050],dist[205050],llst,lst[205050];

void DFS_GetDepth(register int o,register int f)

{

lst[++llst]=o;

for(register int j=ghead[o],t;j;j=gnext[j])

if((t=gnode[j])!=f && !vis[t])

{

depth[t]=depth[o]+gval[j],dist[t]=dist[o]+1;

DFS_GetDepth(t,o);

}

struct _comp

{

bool operator () (const int&a,const int&b)

{

return depth[a]<depth[b];

}

};

int ans[205050];

inline void CalcAns(register int o,register int diff=0,register int delta=1)

{

depth[o]=diff,dist[o]=(delta<0);

llst=0,DFS_GetDepth(o,0);

std::sort(&lst[1],&lst[llst+1],_comp());

while(l<r)

{

while(l<r && depth[lst[l]]+depth[lst[r]] > K)

r--;

for(register int j=r;depth[lst[l]]+depth[lst[j]]==K && j>l;j--)

ans[dist[lst[l]]+dist[lst[j]]]+=delta;

l++;

}

void DFS(register int o)

{

CalcAns(o);

vis[o]=true;

for(register int j=ghead[o],t;j;j=gnext[j])

if(!vis[t=gnode[j]])

{

CalcAns(t,gval[j],-1);

asize=size[t],root=mxsroot=0,DFS_GetRoot(t,0);

DFS(root);

}

int main()

{

::K=K;

for(register int i=1;i<=N-1;i++)

{

insertLine(a,b,v);

}

asize=N,root=mxsroot=0,DFS_GetRoot(1,0);

DFS(root);

for(register int i=1;i<=N;i++)

if(ans[i])

{

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

return 0;

}

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

return 0;

}

YZOJ P3924 [IOI2011]Race

题目描述

输入格式

输出格式

样例输入

样例输出

发表回复 取消回复

发表回复取消回复