「BZOJ3694」「FJ2014集训」最短路

2014年7月20日5,2190

题目描述

给出一个n个点m条边的无向图，n个点的编号从1~n，定义源点为1。定义最短路树如下：从源点1经过边集T到任意一点i有且仅有一条路径，且这条路径是整个图1到i的最短路径，边集T构成最短路树。

给出最短路树，求对于除了源点1外的每个点i，求最短路，要求不经过给出的最短路树上的1到i的路径的最后一条边。

输入格式

第一行包含两个数n和m，表示图中有n个点和m条边。

接下来m行，每行有四个数ai，bi，li，ti，表示图中第i条边连接ai和bi权值为li，ti为1表示这条边是最短路树上的边，ti为0表示不是最短路树上的边。

输出格式

输出n-1个数，第i个数表示从1到i+1的要求的最短路。无法到达输出-1。

样例输入

5 9

3 1 3 1

1 4 2 1

2 1 6 0

2 3 4 0

5 2 3 0

3 2 2 1

5 3 1 1

3 5 2 0

4 5 4 0

样例输出

6 7 8 5

数据规模

对于30%的数据，n≤100，m≤2000

对于100%的数据，n≤4000，m≤100000，1≤li≤100000

题解

这题是usacp安全路径简化版。。。

而且由于数据是随机的，树的深度是logn T T

所以暴力都能过。。。

我的做法是树链剖分+线段树

对于一条不在最短路树的有向边（无向可看成两条有向）u-v，长度L，设t=lca(u,v)

那么对于t-v的路径上所有点x，都可通过1-t-u-v-x

路径长度为d[u]+L+d[v]-d[x]

最小化这个长度，也就是最小化d[u]+d[v]+L

所以我们可以用这个值去更新t-v所有点（不包括t）的最短路长度

这一步可以用线段树操作。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define inf 1000000000
using namespace std;
inline 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,cnt1,cnt2=1,place;
int bin[12];
int u[100005],v[100005],w[100005];
int dis[100005],deep[100005],son[100005],fa[100005][12];
int pl[100005],belong[100005];
struct data{int to,next,v;}e[100005];int head[100005];
struct seg{int l,r,v,tag;}t[400005];
void ins(int u,int v,int w)
{
	e[++cnt1].to=v;e[cnt1].next=head[u];head[u]=cnt1;e[cnt1].v=w;
}
void insert(int u,int v,int w)
{
	ins(u,v,w);ins(v,u,w);
}
void dfs1(int x,int f)
{
	for(int i=1;i<=11;i++)
	    if(bin[i]<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];
	    else break;
	son[x]=1;
	for(int i=head[x];i;i=e[i].next)
	{
		if(e[i].to==f)continue;
		deep[e[i].to]=deep[x]+1;
		fa[e[i].to][0]=x;
		dis[e[i].to]=dis[x]+e[i].v;
		dfs1(e[i].to,x);
		son[x]+=son[e[i].to];
	}
}
void dfs2(int x,int chain)
{
	belong[x]=chain;place++;pl[x]=place;
	int k=0;
	for(int i=head[x];i;i=e[i].next)
		if(deep[e[i].to]>deep[x]&&son[e[i].to]>son[k])
		    k=e[i].to;
	if(k)dfs2(k,chain);
	for(int i=head[x];i;i=e[i].next)
	    if(deep[e[i].to]>deep[x]&&e[i].to!=k)
	        dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	int t=deep[x]-deep[y];
	for(int i=0;i<=11;i++)
	    if(bin[i]&t)x=fa[x][i];
	for(int i=11;i>=0;i--)
	   if(fa[x][i]!=fa[y][i])
	      x=fa[x][i],y=fa[y][i];
	if(x==y)return x;
	return fa[x][0];
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;t[k].tag=inf;
	if(l==r){t[k].v=inf;return;}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void pushdown(int k)
{
	if(t[k].tag==inf||t[k].l==t[k].r)return;
	int tag=t[k].tag;t[k].tag=inf;
	t[k<<1].tag=min(t[k<<1].tag,tag);
	t[k<<1|1].tag=min(t[k<<1|1].tag,tag);
	if(t[k<<1].l==t[k<<1].r)t[k<<1].v=min(t[k<<1].v,tag);
	if(t[k<<1|1].l==t[k<<1|1].r)t[k<<1|1].v=min(t[k<<1|1].v,tag);
}
void update(int k,int x,int y,int v)
{
	pushdown(k);
    int l=t[k].l,r=t[k].r;
	if(x==l&&y==r)
	{
		t[k].tag=min(t[k].tag,v);
		if(l==r)t[k].v=min(v,t[k].v);
		return;
	}
	int mid=(l+r)>>1;
	if(y<=mid)update(k<<1,x,y,v);
	else if(x>mid)update(k<<1|1,x,y,v);
	else {update(k<<1,x,mid,v);update(k<<1|1,mid+1,y,v);}
}
int ask(int k,int x)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==r)return t[k].v;
	int mid=(l+r)>>1;
	if(x<=mid)return ask(k<<1,x);
	else return ask(k<<1|1,x);
}
void solveupdate(int x,int f,int v)
{
	while(belong[x]!=belong[f])
	{
		update(1,pl[belong[x]],pl[x],v);
		x=fa[belong[x]][0];
	}
	if(x!=f)update(1,pl[f]+1,pl[x],v);
}
void solve()
{
	build(1,1,n);
	for(int i=1;i<cnt2;i++)
	{
		int t=lca(u[i],v[i]);
		solveupdate(u[i],t,dis[u[i]]+dis[v[i]]+w[i]);
		solveupdate(v[i],t,dis[u[i]]+dis[v[i]]+w[i]);
	}
	for(int i=2;i<=n;i++)
	{
		int t=ask(1,pl[i]);
		if(t!=inf)printf("%d ",t-dis[i]);
	    else printf("-1 ");
	}
}
int main()
{
	//freopen("shortest.in","r",stdin);
	//freopen("shortest.out","w",stdout);
	bin[0]=1;for(int i=1;i<=12;i++)bin[i]=bin[i-1]*2;
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
	    u[cnt2]=read();v[cnt2]=read(),w[cnt2]=read();
		bool f=read();
	    if(!f)cnt2++;
	    else insert(u[cnt2],v[cnt2],w[cnt2]);
	}
	dfs1(1,0);dfs2(1,1);
	solve();
	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

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<cstring>

#define ll long long

#define inf 1000000000

using namespace std;

inline 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,cnt1,cnt2=1,place;

int bin[12];

int u[100005],v[100005],w[100005];

int dis[100005],deep[100005],son[100005],fa[100005][12];

int pl[100005],belong[100005];

struct data{int to,next,v;}e[100005];int head[100005];

struct seg{int l,r,v,tag;}t[400005];

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

{

e[++cnt1].to=v;e[cnt1].next=head[u];head[u]=cnt1;e[cnt1].v=w;

}

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

{

ins(u,v,w);ins(v,u,w);

}

void dfs1(int x,int f)

{

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

if(bin[i]<=deep[x])fa[x][i]=fa[fa[x][i-1]][i-1];

else break;

son[x]=1;

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

{

if(e[i].to==f)continue;

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

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

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

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

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

}

void dfs2(int x,int chain)

{

belong[x]=chain;place++;pl[x]=place;

int k=0;

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

if(deep[e[i].to]>deep[x]&&son[e[i].to]>son[k])

k=e[i].to;

if(k)dfs2(k,chain);

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

if(deep[e[i].to]>deep[x]&&e[i].to!=k)

dfs2(e[i].to,e[i].to);

}

int lca(int x,int y)

{

if(deep[x]<deep[y])swap(x,y);

int t=deep[x]-deep[y];

for(int i=0;i<=11;i++)

if(bin[i]&t)x=fa[x][i];

for(int i=11;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;t[k].tag=inf;

if(l==r){t[k].v=inf;return;}

int mid=(l+r)>>1;

build(k<<1,l,mid);build(k<<1|1,mid+1,r);

}

void pushdown(int k)

{

if(t[k].tag==inf||t[k].l==t[k].r)return;

int tag=t[k].tag;t[k].tag=inf;

t[k<<1].tag=min(t[k<<1].tag,tag);

t[k<<1|1].tag=min(t[k<<1|1].tag,tag);

if(t[k<<1].l==t[k<<1].r)t[k<<1].v=min(t[k<<1].v,tag);

if(t[k<<1|1].l==t[k<<1|1].r)t[k<<1|1].v=min(t[k<<1|1].v,tag);

}

void update(int k,int x,int y,int v)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(x==l&&y==r)

{

t[k].tag=min(t[k].tag,v);

if(l==r)t[k].v=min(v,t[k].v);

return;

}

int mid=(l+r)>>1;

if(y<=mid)update(k<<1,x,y,v);

else if(x>mid)update(k<<1|1,x,y,v);

else {update(k<<1,x,mid,v);update(k<<1|1,mid+1,y,v);}

}

int ask(int k,int x)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==r)return t[k].v;

int mid=(l+r)>>1;

if(x<=mid)return ask(k<<1,x);

else return ask(k<<1|1,x);

}

void solveupdate(int x,int f,int v)

{

while(belong[x]!=belong[f])

{

update(1,pl[belong[x]],pl[x],v);

x=fa[belong[x]][0];

}

if(x!=f)update(1,pl[f]+1,pl[x],v);

}

void solve()

{

build(1,1,n);

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

{

int t=lca(u[i],v[i]);

solveupdate(u[i],t,dis[u[i]]+dis[v[i]]+w[i]);

solveupdate(v[i],t,dis[u[i]]+dis[v[i]]+w[i]);

}

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

{

int t=ask(1,pl[i]);

if(t!=inf)printf("%d ",t-dis[i]);

else printf("-1 ");

}

int main()

{

//freopen("shortest.in","r",stdin);

//freopen("shortest.out","w",stdout);

bin[0]=1;for(int i=1;i<=12;i++)bin[i]=bin[i-1]*2;

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

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

{

u[cnt2]=read();v[cnt2]=read(),w[cnt2]=read();

bool f=read();

if(!f)cnt2++;

else insert(u[cnt2],v[cnt2],w[cnt2]);

}

dfs1(1,0);dfs2(1,1);

solve();

return 0;

}

« 「FJ2014集训」信心题「BZOJ3693」「FJ2014集训」圆桌会议 »

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

「BZOJ3694」「FJ2014集训」最短路

分类目录

热门文章

Myfriends

近期评论