用dedecms做两个一样的网站,办公空间设计说明范文,广州seo服务外包,网络舆情案例[NOI2018] 归程descriptionsolution1code1solution2codedescription
题目描述
本题的故事发生在魔力之都#xff0c;在这里我们将为你介绍一些必要的设定
魔力之都可以抽象成一个nnn个节点、mmm条边的无向连通图#xff08;节点的编号从111至nnn#xff09;我们依次用 l,…
[NOI2018] 归程descriptionsolution1code1solution2codedescription
题目描述
本题的故事发生在魔力之都在这里我们将为你介绍一些必要的设定
魔力之都可以抽象成一个nnn个节点、mmm条边的无向连通图节点的编号从111至nnn我们依次用 l,al,al,a描述一条边的长度、海拔
作为季风气候的代表城市魔力之都时常有雨水相伴因此道路积水总是不可避免的。由于整个城市的排水系统连通因此有积水的边一定是海拔相对最低的一些边
我们用水位线来描述降雨的程度它的意义是所有海拔不超过水位线的边都是有积水的
Yazid 是一名来自魔力之都的 OIer刚参加完 ION2018 的他将踏上归程回到他温暖的家
Yazid 的家恰好在魔力之都的111号节点。对于接下来 Q 天每一天 Yazid 都会告诉你他的出发点 v以及当天的水位线 p
每一天Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边
Yazid 可以在任意节点下车这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
需要特殊说明的是第二天车会被重置这意味着 车会在新的出发点被准备好。Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行因此他希望在完成回家这一目标的同时最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算
本题的部分测试点将强制在线具体细节请见「输入格式」和「子任务」。
输入格式
从文件 return.in 读入数据
单个测试点中包含多组数据。输入的第一行为一个非负整数 T表示数据的组数。
接下来依次描述每组数据对于每组数据
第一行2个非负整数 n,m分别表示节点数、边数。
接下来 m行每行4个正整数 u,v,l,a描述一条连接节点 u,v 的、长度为 l、海拔为 a 的边。在这里我们保证 1≤u,v≤n
接下来一行3个非负数 Q,K,S其中Q表示总天数K∈0,1是一个会在下面被用到的系数S 表示的是可能的最高水位线。
接下来 Q 行依次描述每天的状况。每行2个整数 v0,p0 描述一天 这一天的出发节点为 v(v0K×lastans−1)modn1 这一天的水位线为 p(p0K×lastans)mod(S1)
其中 lastans 表示上一天的答案最小步行总路程
特别地我们规定第 1 天 lastans0
在这里我们保证 1≤v0≤n,0≤p0≤S
对于输入中的每一行如果该行包含多个数则用单个空格将它们隔开。
输出格式
输出到文件 return.out 中。
依次输出各组数据的答案。对于每组数据
输出 Q 行每行一个整数依次表示每天的最小步行总路程
样例
样例 1
1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 20
50
200
50
150第一天没有降水Yazid 可以坐车直接回到家中。
第二天、第三天、第四天的积水情况相同均为连接 1,2 号节点的边、连接 3,4 号点的边有积水。
对于第二天Yazid 从 2 号点出发坐车只能去往 3 号节点对回家没有帮助。因此 Yazid 只能纯靠徒步回家。
对于第三天从 4 号节点出发的唯一一条边是有积水的车也就变得无用了。Yazid 只能纯靠徒步回家。
对于第四天Yazid 可以坐车先到达 2 号节点再步行回家。
第五天所有的边都积水了因此 Yazid 只能纯靠徒步回家。
样例 2
1
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 00
2
3
1本组数据强制在线。
第一天的答案是 0因此第二天的 v(50−1)mod515,p(20)mod(31)2
第二天的答案是 2因此第三天的 v(22−1)mod514,p(02)mod(31)2
第三天的答案是 3因此第四天的 v(43−1)mod512,p(03)mod(31)3
数据范围与提示
所有测试点均保证 T≤3所有测试点中的所有数据均满足如下限制
n≤2×105m≤4×105Q≤4×105K∈0,11≤S≤109
对于所有边l≤104a≤109
任意两点之间都直接或间接通过边相连。
solution1 考虑没有一条边被淹。那就是000 考虑边都被淹了。那就是问从起点到111的最短路 考虑淹了一些边。没有淹的边可以随便走相当于是个连通块 所以就是求从起点所在连通块到111所在连通块的最短路
显然边的存在跟每次给定的水位线有关似乎只能在线维护了。
实则不然如果我们将所有水位线的答案都提前处理出来那么在线也就是离线了
这就是我们的——可持久化
最短路可以最开始跑一遍dijkstra解决
连通块就是并查集问题再加上iii所在块到111的最短路就用线段树维护
具体而言将所有边的水位从低到高排序从后往前加入每一条边
对于第iii号版本的线段树维护的是所有海拔大于等于该边构成的连通块以及在此时生成的图上每个点到111的最短路
初始时每个点自己为一个连通块t[now].fal,t[now].ansdis[l]
一旦合并两个连通块按秩合并就在线段树上新建版本并修改t[now].faNew_fa
如果新儿子最短路优于父亲最短路就又新建版本修改t[now].ansans
感觉有可能新建了两个版本NO
并查集修改是更改儿子v对应的父亲新建的log\loglog个点是v一路上的
而答案更新是要更新父亲u对应的答案就又要新建log\loglog个u一路上的点
属于同一个版本root[i]
相当于在上一条边对应的版本线段树基础上一共修改2log2\log2log个点成为新的版本
最后就是询问直接找比所给水位线严格大于的所有高度都存在的版本
就是用upper_bound()找一下而已啦
code1
#include queue
#include cstdio
#include vector
#include cstring
#include iostream
#include algorithm
using namespace std;
#define maxn 400005
#define int long long
#define Pair pair int, int
priority_queue Pair, vector Pair , greater Pair q;
struct node { int l, r, fa, ans, h; }t[maxn * 20];
struct edge { int u, v, len, h; }E[maxn];
vector edge G[maxn];
int n, m, Q, K, S, cnt;
int dis[maxn], root[maxn], high[maxn];
bool vis[maxn];void dijkstra() {memset( vis, 0, sizeof( vis ) );memset( dis, 0x7f, sizeof( dis ) );q.push( make_pair( dis[1] 0, 1 ) );while( ! q.empty() ) {int u q.top().second; q.pop();if( vis[u] ) continue;vis[u] 1;for( int i 0;i G[u].size();i ) {int v G[u][i].v, len G[u][i].len;if( dis[u] len dis[v] ) {dis[v] dis[u] len;q.push( make_pair( dis[v], v ) );}}}
}void build( int now, int l, int r ) {now cnt;if( l r ) { t[now].fa l, t[now].ans dis[l], t[now].h 0; return; }int mid ( l r ) 1;build( t[now].l, l, mid );build( t[now].r, mid 1, r );
}int query( int now, int l, int r, int pos ) {if( l r ) return now;int mid ( l r ) 1;if( pos mid ) return query( t[now].l, l, mid, pos );else return query( t[now].r, mid 1, r, pos );
}int find( int rt, int x ) {int now query( rt, 1, n, x );while( t[now].fa ^ x ) {x t[now].fa;now query( rt, 1, n, x );}return now;
}void modify( int now, int lst, int l, int r, int pos, int New_fa ) {t[now cnt] t[lst];if( l r ) { t[now].fa New_fa; return; }int mid ( l r ) 1;if( pos mid ) modify( t[now].l, t[lst].l, l, mid, pos, New_fa );else modify( t[now].r, t[lst].r, mid 1, r, pos, New_fa );
}void update( int now, int lst, int l, int r, int pos, int ans ) {t[now cnt] t[lst];if( l r ) { t[now].ans ans; return; }int mid ( l r ) 1;if( pos mid ) update( t[now].l, t[lst].l, l, mid, pos, ans );else update( t[now].r, t[lst].r, mid 1, r, pos, ans );
}void modify( int now, int l, int r, int pos ) {if( l r ) { t[now].h ; return; }int mid ( l r ) 1;if( pos mid ) modify( t[now].l, l, mid, pos );else modify( t[now].r, mid 1, r, pos );
}signed main() {
// freopen( return.in, r, stdin );
// freopen( return.out, w, stdout );int T;scanf( %lld, T );while( T -- ) {scanf( %lld %lld, n, m );for( int i 1;i n;i ) G[i].clear();for( int i 1, u, v, l, a;i m;i ) {scanf( %lld %lld %lld %lld, u, v, l, a );G[u].push_back( { u, v, l, a } );G[v].push_back( { u, u, l, a } );E[i] { u, v, l, a };high[i] a;}dijkstra();sort( E 1, E m 1, []( edge x, edge y ) { return x.h y.h; } );sort( high 1, high m 1 );int now m;m unique( high 1, high m 1 ) - high - 1;cnt 0;build( root[m 1], 1, n );for( int i m;i;i -- ) {root[i] root[i 1];while( E[now].h high[i] ) {int u find( root[i], E[now].u );int v find( root[i], E[now].v );if( t[u].fa ^ t[v].fa ) {if( t[u].h t[v].h ) swap( u, v ); //并查集按(秩)树高合并modify( root[i], root[i], 1, n, t[v].fa, t[u].fa );if( t[v].ans t[u].ans )update( root[i], root[i], 1, n, t[u].fa, t[v].ans );//新加入的v带来更小的新答案if( t[u].h t[v].h )modify( root[i], 1, n, t[u].fa );}now --;}}scanf( %lld %lld %lld, Q, K, S );int v, p, lastans 0;while( Q -- ) {scanf( %lld %lld, v, p );v ( v K * lastans - 1 ) % n 1;p ( p K * lastans ) % ( S 1 );p upper_bound( high 1, high m 1, p ) - high;printf( %lld\n, lastans t[find( root[p], v )].ans );}}return 0;
}solution2
将边权按海拔高度从大到小排序然后kruskal重构树显然这个重构树是小根堆
所以如果询问海拔小于询问点某个祖先的权值意味着这个祖先的子树内所有点都是可以开车到达的那么其实就是询问这个祖先子树内的点到111的最短路
怎么找个祖先就可以用倍增来找了
code
#include queue
#include cstdio
#include vector
#include cstring
#include iostream
#include algorithm
using namespace std;
#define maxn 400005
#define int long long
#define Pair pair int, int
vector int G[maxn];
priority_queue Pair, vector Pair , greater Pair q;
struct node { int u, v, h; }E[maxn];
int head[maxn], to[maxn 1], nxt[maxn 1], len[maxn 1];
int first[maxn], End[maxn], enxt[maxn];
int T, n, m, cnt, cntt;
int dis[maxn], fa[maxn], val[maxn], ans[maxn];
int f[maxn][20];void addedge( int u, int v, int w ) {to[cnt] v, nxt[cnt] head[u], len[cnt] w, head[u] cnt ;
}int find( int x ) { return fa[x] x ? x : fa[x] find( fa[x] ); }void dijkstra() {for( int i 1;i n;i ) dis[i] 1e18;q.push( make_pair( dis[1] 0, 1 ) );while( ! q.empty() ) {int now q.top().second, d q.top().first; q.pop();if( d ^ dis[now] ) continue;for( int i head[now];~ i;i nxt[i] )if( dis[to[i]] dis[now] len[i] ) {dis[to[i]] dis[now] len[i];q.push( make_pair( dis[to[i]], to[i] ) );}}for( int i 1;i n;i ) ans[i] dis[i];
}void addedge( int u, int v ) {End[cntt] v, enxt[cntt] first[u], first[u] cntt ;
}void kruskal() {sort( E 1, E m 1, []( node x, node y ) { return x.h y.h; } );for( int i 1;i n;i ) fa[i] i;cnt n;for( int i 1, tot 0;i m;i ) {int u E[i].u, v E[i].v;int fu find( u ), fv find( v );if( fu ^ fv ) { cnt;val[cnt] E[i].h;fa[cnt] fa[fu] fa[fv] cnt;addedge( cnt, fu );addedge( cnt, fv );tot ;if( tot n - 1 ) break;}}
}void dfs( int u ) {for( int i 1;i 20;i )f[u][i] f[f[u][i - 1]][i - 1];for( int i first[u];~ i;i enxt[i] ) {int v End[i];f[v][0] u;dfs( v );ans[u] min( ans[u], ans[v] );}
}void read( int x ) {x 0;char s getchar();while( s 0 or s 9 ) s getchar();while( 0 s and s 9 ) x ( x 1 ) ( x 3 ) ( s ^ 48 ), s getchar();
}signed main() {freopen( return.in, r, stdin );freopen( return.out, w, stdout );read( T );while( T -- ) {read( n ), read( m );cnt cntt 0;for( int i 1;i n;i ) {head[i] first[i] first[i n] -1;for( int j 0;j 20;j ) f[i][j] 0;} for( int i n 1;i ( n 1 );i ) G[i].clear();for( int i 1, u, v, l, h;i m;i ) {read( u ), read( v ), read( l ), read( h );E[i] { u, v, h };addedge( u, v, l );addedge( v, u, l );}dijkstra();kruskal();for( int i n 1;i cnt;i ) ans[i] 1e18;dfs( cnt );int Q, K, S, v, p, lst 0;read( Q ), read( K ), read( S );while( Q -- ) {read( v ), read( p );v ( v K * lst - 1 ) % n 1;p ( p K * lst ) % ( S 1 );for( int i 19;~ i;i -- )if( val[f[v][i]] p ) v f[v][i];printf( %lld\n, lst ans[v] );}}return 0;
}
