「BZOJ4016」[FJOI2014] 最短路径树问题

2014年12月15日7,9285

cxjyxx_me:

先求一个最短路图然后再这个图上dfs 对于一个点的所有出点按编号从小到大dfs
这样可以保证dfs树就是题目要求的树
然后在这棵树上跑树分治 f[i][j][2]表示前i棵子树从根出发链长为j [0：最长长度][1:这个长度条件下的方案数]
对于第i+1棵子树单独跑一个f’[i][j][2]意义一样枚举这颗子树上链长和f一起更新答案然后用f‘更新f

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#define pa pair<int,int>
#define inf 2000000000
#define ll long long 
#define mod 1000000007
using namespace std;
inline int read()
{
    int 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 ans1,ans2;
int n,m,K,cnt;
int rt,sum;
int dis[30005],last[30005],last2[30005],from[30005];
int mx[30005],size[30005],deep[30005],q[30005],fa[30005];
bool vis[30005];
priority_queue<pa,vector<pa>,greater<pa> >heap;
struct edge{
	int to,next,v;
}ed[120005],e[60005];
int f[30005][2],g[30005][2];
vector<pa> to[30005];
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 insert2(int u,int v,int w)
{
	ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;ed[cnt].v=w;
}
void dfs(int x)
{
	vis[x]=1;
	for(int i=last2[x];i;i=ed[i].next)
		if(!vis[ed[i].to]&&dis[x]+ed[i].v==dis[ed[i].to])
		{
			insert(x,ed[i].to,ed[i].v);
			dfs(ed[i].to);
		}
}
void dijkstra()
{
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[1]=1;
	heap.push(make_pair(0,1));
	while(!heap.empty())
	{
		int now=heap.top().second;heap.pop();
		if(vis[now])continue;
		vis[now]=1;
		for(int i=last2[now];i;i=ed[i].next)
			if(dis[now]+ed[i].v<dis[ed[i].to])
			{
				dis[ed[i].to]=dis[now]+ed[i].v;
				from[ed[i].to]=i;
				heap.push(make_pair(dis[ed[i].to],ed[i].to));
			}
	}
}
void getroot(int x)
{
	size[x]=1;mx[x]=0;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to]&&e[i].to!=fa[x])
		{
			fa[e[i].to]=x;
			getroot(e[i].to);
			mx[x]=max(mx[x],size[e[i].to]);
			size[x]+=size[e[i].to];
		}
	mx[x]=max(mx[x],sum-size[x]);
	if(mx[x]<mx[rt])rt=x;
}
void solve(int x,int S)
{
	vis[x]=1;f[0][1]=1;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			int head=0,tail=1;
			q[0]=e[i].to;
			deep[e[i].to]=1;fa[e[i].to]=x;
			dis[e[i].to]=e[i].v;
			while(head!=tail)
			{
				int now=q[head];head++;
				int k=deep[now];
				if(k>K)break;
				if(dis[now]>g[k][0])
					g[k][0]=dis[now],g[k][1]=0;
				if(dis[now]==g[k][0])g[k][1]++;
				for(int j=last[now];j;j=e[j].next)
					if(!vis[e[j].to]&&e[j].to!=fa[now])
					{
						fa[e[j].to]=now;
						deep[e[j].to]=deep[now]+1;
						dis[e[j].to]=dis[now]+e[j].v;
						q[tail++]=e[j].to;
					}
			}
			for(int j=1;j<=K;j++)
			{
				if(g[j][0]+f[K-j][0]>ans1)
					ans1=g[j][0]+f[K-j][0],ans2=0;
				if(g[j][0]+f[K-j][0]==ans1)
					ans2+=g[j][1]*f[K-j][1];
			}
			for(int j=1;j<=K;j++)
			{
				if(g[j][0]>f[j][0])f[j][0]=g[j][0],f[j][1]=0;
				if(g[j][0]==f[j][0])f[j][1]+=g[j][1];
				g[j][0]=g[j][1]=0;
			}
		}
	for(int j=0;j<=K;j++)f[j][0]=f[j][1]=0;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			sum=size[e[i].to];
			if(size[e[i].to]>size[x])size[e[i].to]=S-size[e[i].to];
			rt=0;
			if(sum>=K)getroot(e[i].to);
			solve(rt,size[e[i].to]);
		}
}
int main()
{
	n=read();m=read();K=read();K--;
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		to[u].push_back(make_pair(v,w));
		to[v].push_back(make_pair(u,w));
	}
	for(int i=1;i<=n;i++)
	{
		sort(to[i].begin(),to[i].end());
		for(int t=to[i].size()-1;t>=0;t--)
			insert2(i,to[i][t].first,to[i][t].second);
	}
	dijkstra();
	cnt=0;
	memset(vis,0,sizeof(vis));
	dfs(1);
	memset(vis,0,sizeof(vis));
	rt=0;mx[0]=inf;sum=n;
	getroot(1);solve(rt,sum);
	printf("%d %d\n",ans1,ans2);
	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

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#define pa pair<int,int>

#define inf 2000000000

#define ll long long

#define mod 1000000007

using namespace std;

inline int read()

{

int 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 ans1,ans2;

int n,m,K,cnt;

int rt,sum;

int dis[30005],last[30005],last2[30005],from[30005];

int mx[30005],size[30005],deep[30005],q[30005],fa[30005];

bool vis[30005];

priority_queue<pa,vector<pa>,greater<pa> >heap;

struct edge{

int to,next,v;

}ed[120005],e[60005];

int f[30005][2],g[30005][2];

vector<pa> to[30005];

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 insert2(int u,int v,int w)

{

ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;ed[cnt].v=w;

}

void dfs(int x)

{

vis[x]=1;

for(int i=last2[x];i;i=ed[i].next)

if(!vis[ed[i].to]&&dis[x]+ed[i].v==dis[ed[i].to])

{

insert(x,ed[i].to,ed[i].v);

dfs(ed[i].to);

}

void dijkstra()

{

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

dis[1]=1;

heap.push(make_pair(0,1));

while(!heap.empty())

{

int now=heap.top().second;heap.pop();

if(vis[now])continue;

vis[now]=1;

for(int i=last2[now];i;i=ed[i].next)

if(dis[now]+ed[i].v<dis[ed[i].to])

{

dis[ed[i].to]=dis[now]+ed[i].v;

from[ed[i].to]=i;

heap.push(make_pair(dis[ed[i].to],ed[i].to));

}

void getroot(int x)

{

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

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

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

{

fa[e[i].to]=x;

getroot(e[i].to);

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

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

}

mx[x]=max(mx[x],sum-size[x]);

if(mx[x]<mx[rt])rt=x;

}

void solve(int x,int S)

{

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

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

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

{

int head=0,tail=1;

q[0]=e[i].to;

deep[e[i].to]=1;fa[e[i].to]=x;

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

while(head!=tail)

{

int now=q[head];head++;

int k=deep[now];

if(k>K)break;

if(dis[now]>g[k][0])

g[k][0]=dis[now],g[k][1]=0;

if(dis[now]==g[k][0])g[k][1]++;

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

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

{

fa[e[j].to]=now;

deep[e[j].to]=deep[now]+1;

dis[e[j].to]=dis[now]+e[j].v;

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

}

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

{

if(g[j][0]+f[K-j][0]>ans1)

ans1=g[j][0]+f[K-j][0],ans2=0;

if(g[j][0]+f[K-j][0]==ans1)

ans2+=g[j][1]*f[K-j][1];

}

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

{

if(g[j][0]>f[j][0])f[j][0]=g[j][0],f[j][1]=0;

if(g[j][0]==f[j][0])f[j][1]+=g[j][1];

g[j][0]=g[j][1]=0;

}

for(int j=0;j<=K;j++)f[j][0]=f[j][1]=0;

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

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

{

sum=size[e[i].to];

if(size[e[i].to]>size[x])size[e[i].to]=S-size[e[i].to];

rt=0;

if(sum>=K)getroot(e[i].to);

solve(rt,size[e[i].to]);

}

int main()

{

n=read();m=read();K=read();K--;

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

{

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

to[u].push_back(make_pair(v,w));

to[v].push_back(make_pair(u,w));

}

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

{

sort(to[i].begin(),to[i].end());

for(int t=to[i].size()-1;t>=0;t--)

insert2(i,to[i][t].first,to[i][t].second);

}

dijkstra();

cnt=0;

memset(vis,0,sizeof(vis));

dfs(1);

memset(vis,0,sizeof(vis));

rt=0;mx[0]=inf;sum=n;

getroot(1);solve(rt,sum);

printf("%d %d\n",ans1,ans2);

return 0;

}

« 「BZOJ2802」[POI2012] Warehouse Store NOI2010海拔 »

一个人看日落

黄学长~貌似第131行那个应该是S – size[x]意义才对的样子Orz，虽然不知道为什么改不改交BZOJ都是可以过的。

WuHongxun

TAT求题面

hzwer

没有的说T T

ShinriiTin

黄学长，求这题题号

hzwer

没有。。。我以前有数据现在不见了

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

「BZOJ4016」[FJOI2014] 最短路径树问题

分类目录

热门文章

Myfriends

近期评论