「小奇模拟赛2」[BZOJ3784] 小奇的树

2016年5月22日7,8512

「题目背景」

小奇在研究树时，遇到了一个难题。

「问题描述」

给定一棵n个节点的树，求前m条最长路径的长度。

「输入格式」

第1行2个整数n，m。

接下来n-1行，每行3个整数u，v，l，表示u，v之间有一条长度为l的边。

「输出格式」

m行如题，从大到小输出。

「样例输入」

4 2

1 2 1

1 3 2

1 4 3

「样例输出」

「数据范围」

序号	n	m	数据类型
1	10	3	暴力
2	233	23333	暴力
3	2000	300000	暴力
4	2000	300000	暴力
5	50000	1	随机生成
6	7798	17798	随机生成
7	7798	27798	随机生成
8	7798	37798	随机生成
9	50000	300000	1-n顺序输入的链
10	50000	300000	以1为根的菊花图

所有的数据及答案均为不超过int范围的正整数

「题解」

这题是bzoj3784的弱化版

原题是给定一棵n个点的树(n <= 50000)，求出树上距离前m大的路径长度(m <= 300000)。

对于40%的数据，bfs加堆或者排序咯。。。

随机生成的数据，可以用点分治加上一些优先队列的奇技淫巧，然而这不是重点

还是来说说原题吧QAQ

1.二分+点分治

二分m大的路径长度，得到下界以后显然是一个nlog^2的经典点分治，加上二分的log，显然比较虚。但是点分治中有一个log是sort需要的，我们就可以先一次点分治把sort的结果用vector存下来，这样的话就能把总复杂度降为nlog^2，得到m大的路径最后一次点分治暴力统计路径。

2.点分治+堆

考虑超级钢琴的做法，点分治时依次扫每棵子树，若将当前子树内的点作为路径的一个端点，另一个端点可以落在一个点分治序列的区间内（之前扫过的子树），这样得出一个长度为nlogn的点分治序列，加上每个点所对应的区间，然后就完全转为超级钢琴的问题了

暴力40

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define pi acos(-1)
#define eps 1e-13
#define mod 10000007
#define inf 2147483647
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt;
int dis[5005][5005];
int q[5005],last[50005];
struct data{
    int to,next,v;
}e[100005];
void insert(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].next=last[u];e[cnt].v=w;last[u]=cnt;
    e[++cnt].to=u;e[cnt].next=last[v];e[cnt].v=w;last[v]=cnt;    
} 
void getdis(int x)
{
    int head=0,tail=1;
    q[0]=x;
    for(int i=1;i<=n;i++)
        if(i!=x)dis[x][i]=inf;
    while(head!=tail)
    {
        int now=q[head++];
        for(int i=last[now];i;i=e[i].next)
            if(dis[x][e[i].to]==inf)
            {            
                dis[x][e[i].to]=dis[x][now]+e[i].v;
                q[tail++]=e[i].to;
            }
    }
}
priority_queue<int,vector<int> >pq;
void solve1()
{
    for(int i=1;i<=n;i++)
        getdis(i);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            pq.push(dis[i][j]);
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",pq.top());
        pq.pop();
    }
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n-1;i++)
    {
        int u=read(),v=read(),w=read();
        insert(u,v,w);
    }
    if(n<=2000)solve1();
    return 0;
}

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define pi acos(-1)

#define eps 1e-13

#define mod 10000007

#define inf 2147483647

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt;

int dis[5005][5005];

int q[5005],last[50005];

struct data{

int to,next,v;

}e[100005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];e[cnt].v=w;last[u]=cnt;

e[++cnt].to=u;e[cnt].next=last[v];e[cnt].v=w;last[v]=cnt;

}

void getdis(int x)

{

int head=0,tail=1;

q[0]=x;

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

if(i!=x)dis[x][i]=inf;

while(head!=tail)

{

int now=q[head++];

for(int i=last[now];i;i=e[i].next)

if(dis[x][e[i].to]==inf)

{

dis[x][e[i].to]=dis[x][now]+e[i].v;

q[tail++]=e[i].to;

}

priority_queue<int,vector<int> >pq;

void solve1()

{

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

getdis(i);

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

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

pq.push(dis[i][j]);

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

{

printf("%d\n",pq.top());

pq.pop();

}

int main()

{

freopen("tree.in","r",stdin);

freopen("tree.out","w",stdout);

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

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

{

int u=read(),v=read(),w=read();

insert(u,v,w);

}

if(n<=2000)solve1();

return 0;

}

解法2

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define inf 1000000000
#define pa pair<int,int>
using namespace std;
int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
int l,r;
int bin[20],Log[50005];
int n,m,cnt,ind;
int root,tot;
int f[50005],dis[50005],size[50005];
int val[2000005],mx[2000005][20];
pair<int,int> p[2000005];
bool vis[50005];
struct edge{
	int to,next,v;
}e[100005];int last[50005];
struct node{
	int l,r,x,mx;
};
priority_queue<node,vector<node> >q;
bool operator<(node a,node b)
{
	return val[a.mx]+val[a.x]<val[b.mx]+val[b.x];
}
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void getroot(int x,int fa)
{
	size[x]=1;f[x]=0;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa&&!vis[e[i].to])
		{
			getroot(e[i].to,x);
			f[x]=max(f[x],size[e[i].to]);
			size[x]+=size[e[i].to];
		}
	f[x]=max(f[x],tot-size[x]);
	if(f[x]<f[root])root=x;
}
void getdis(int x,int fa)
{
	val[++ind]=dis[x];p[ind]=make_pair(l,r);
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa&&!vis[e[i].to])
		{
			dis[e[i].to]=dis[x]+e[i].v;
			getdis(e[i].to,x);
		}
}
void solve(int x)
{
    val[++ind]=0;p[ind]=make_pair(0,0);
	vis[x]=1;l=r=ind;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			dis[e[i].to]=e[i].v;
			getdis(e[i].to,x);
			r=ind;
		}
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			tot=size[e[i].to];root=0;
			getroot(e[i].to,x);
			solve(root);
		}
}
void pre()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	Log[0]=-1;for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;
	for(int i=1;i<=ind;i++)mx[i][0]=i;
	for(int i=1;i<=Log[n];i++)
		for(int j=1;j<=ind;j++)
			if(j+bin[i]<=ind)
			{
				int t1=mx[j][i-1],t2=mx[j+bin[i-1]][i-1];
				if(val[t1]>val[t2])mx[j][i]=t1;
				else mx[j][i]=t2;
			}
}
int query(int x,int y)
{
	if(x==y)return x;
	int t=Log[y-x+1];
	int t1=mx[x][t],t2=mx[y-bin[t]+1][t];
	if(val[t1]>val[t2])return t1;
	return t2;
}
inline void push(int l,int r,int x)
{
	q.push((node){l,r,x,query(l,r)});
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),w=read();
		insert(u,v,w);
	}
	tot=n;f[0]=n;
	getroot(1,0);
	solve(root);
	pre();
	for(int i=1;i<=ind;i++)
	{
		int l=p[i].first,r=p[i].second;
		if(l)push(l,r,i);
	}
	while(m--)
	{
		node t=q.top();q.pop();
		printf("%d\n",val[t.mx]+val[t.x]);
		if(t.mx+1<=t.r)push(t.mx+1,t.r,t.x);
		if(t.mx-1>=t.l)push(t.l,t.mx-1,t.x);
	}
	return 0;
}

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

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#define inf 1000000000

#define pa pair<int,int>

using namespace std;

int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int l,r;

int bin[20],Log[50005];

int n,m,cnt,ind;

int root,tot;

int f[50005],dis[50005],size[50005];

int val[2000005],mx[2000005][20];

pair<int,int> p[2000005];

bool vis[50005];

struct edge{

int to,next,v;

}e[100005];int last[50005];

struct node{

int l,r,x,mx;

};

priority_queue<node,vector<node> >q;

bool operator<(node a,node b)

{

return val[a.mx]+val[a.x]<val[b.mx]+val[b.x];

}

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

}

void getroot(int x,int fa)

{

size[x]=1;f[x]=0;

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

if(e[i].to!=fa&&!vis[e[i].to])

{

getroot(e[i].to,x);

f[x]=max(f[x],size[e[i].to]);

size[x]+=size[e[i].to];

}

f[x]=max(f[x],tot-size[x]);

if(f[x]<f[root])root=x;

}

void getdis(int x,int fa)

{

val[++ind]=dis[x];p[ind]=make_pair(l,r);

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

if(e[i].to!=fa&&!vis[e[i].to])

{

dis[e[i].to]=dis[x]+e[i].v;

getdis(e[i].to,x);

}

void solve(int x)

{

val[++ind]=0;p[ind]=make_pair(0,0);

vis[x]=1;l=r=ind;

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

if(!vis[e[i].to])

{

dis[e[i].to]=e[i].v;

getdis(e[i].to,x);

r=ind;

}

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

if(!vis[e[i].to])

{

tot=size[e[i].to];root=0;

getroot(e[i].to,x);

solve(root);

}

void pre()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

Log[0]=-1;for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;

for(int i=1;i<=ind;i++)mx[i][0]=i;

for(int i=1;i<=Log[n];i++)

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

if(j+bin[i]<=ind)

{

int t1=mx[j][i-1],t2=mx[j+bin[i-1]][i-1];

if(val[t1]>val[t2])mx[j][i]=t1;

else mx[j][i]=t2;

}

int query(int x,int y)

{

if(x==y)return x;

int t=Log[y-x+1];

int t1=mx[x][t],t2=mx[y-bin[t]+1][t];

if(val[t1]>val[t2])return t1;

return t2;

}

inline void push(int l,int r,int x)

{

q.push((node){l,r,x,query(l,r)});

}

int main()

{

freopen("tree.in","r",stdin);

freopen("tree.out","w",stdout);

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

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

{

int u=read(),v=read(),w=read();

insert(u,v,w);

}

tot=n;f[0]=n;

getroot(1,0);

solve(root);

pre();

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

{

int l=p[i].first,r=p[i].second;

if(l)push(l,r,i);

}

while(m--)

{

node t=q.top();q.pop();

printf("%d\n",val[t.mx]+val[t.x]);

if(t.mx+1<=t.r)push(t.mx+1,t.r,t.x);

if(t.mx-1>=t.l)push(t.l,t.mx-1,t.x);

}

return 0;

}

« 「CF639X」VK Cup 2016 – Round 1 「小奇模拟赛2」小奇的危机 »

hzy

黄学长,链接404了

hzwer

不存在了QAQ

hzwer.com _ Home | http://hzwer.com

「小奇模拟赛2」[BZOJ3784] 小奇的树

分类目录

热门文章

Myfriends

近期评论