当前位置:网站首页>杭电多校-Slipper-(树图转化+虚点建图)
杭电多校-Slipper-(树图转化+虚点建图)
2022-08-04 04:04:00 【可爱美少女】
题意:
就是给你一个以1为根的树,然后每条边有各自的花费。然后小A可以使用任意次魔法,使用一次魔法可以使得深度差为k的两个点可以互相传送,花费为m。然后给你起点和终点,问你最小花费。
思考:
1.看到这种树上问题,我就感觉是树上dp。但是想了想怎么dp呢?这个跳跃是不能更新转移的呀。所以这里树形dp就不可以了。感觉应该是个难题,但是后来过的很多,那么就不是难题了。
2.那么既然感觉树上dp不能做,还求A到B的最短距离,这不就可以建图然后跑最短路。到这里其实就简单了,建图就是建立可以跳跃的哪些点之间要建好图。那么可以先把每个深度的点维护出来,那么深度为a的到深度为a+k的进行建边,如果暴力枚举点点建边这是nn的复杂度。其实可以建立一个虚点,然后a的点集连虚点,右边的点集连虚点。这样复杂度是4n的。一定是有向边有向边的建立。
3.整个图建立出来后,跑一边distra就可以了。如果卡空间卡时间,可以把vector换成邻接表。初始化vector也要最少的初始化,这样时间空间就优化到极致了。当时我虚点建边的时候建立错了,傻逼了,就跑的很慢。以后一定要画一下图,不能直接上去搞,容易出错。
4.当然,这题的建图方式也可以和下一题一样,不用维护vector存这个深度的点。直接让自己连自己的虚点和别人的虚点就行了,这样更快。边更少,虚点更少。
代码:
#include<bits/stdc++.h>
#define ll long long
#define PII pair<ll,int >
#define fi first
#define se second
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const ll N = 1e6+50,inf = 1e18;
int T,n,m,k;
int dep[N];
int st,ed;
ll dist[3*N];
bool vis[3*N]; //卡空间,记得关longlong,开bool
int cnt,maxn;
vector<int > v[N];
vector<PII > e[3*N];
void dfs(int now,int p)
{
dep[now] = dep[p]+1;
v[dep[now]].pb(now);
maxn = max(maxn,dep[now]);
for(auto t:e[now])
{
int spot = t.fi;
if(spot==p) continue;
dfs(spot,now);
}
}
void distra()
{
for(int i=1;i<=cnt;i++) dist[i] = inf,vis[i] = 0;
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({
0,st});
dist[st] = 0;
while(q.size())
{
auto t = q.top();q.pop();
int now = t.se,dis = t.fi;
if(vis[now]) continue;
vis[now] = 1;
for(auto tt:e[now])
{
int spot = tt.fi,w = tt.se;
if(dist[spot]>dist[now]+w)
{
dist[spot] = dist[now]+w;
q.push({
dist[spot],spot});
}
}
}
}
signed main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) v[i].clear(); //最少的初始化
for(int i=1;i<=cnt;i++) e[i].clear(); //最少的初始化,用多少,初始化多少
for(int i=1;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[a].pb({
b,c});
e[b].pb({
a,c});
}
scanf("%d%d%d%d",&k,&m,&st,&ed);
dfs(1,0);
cnt = n; //cnt最大3*n
for(int i=1;i<=n;i++)
{
int r = i+k;
if(r>maxn) break; //如果深度为r的没有,就提前退出,下面的就不建边了,浪费。
cnt++;
for(auto t:v[i]) e[t].pb({
cnt,m});
for(auto t:v[r]) e[cnt].pb({
t,0});
cnt++;
for(auto t:v[r]) e[t].pb({
cnt,m});
for(auto t:v[i]) e[cnt].pb({
t,0});
}
distra();
printf("%lld\n",dist[ed]);
}
return 0;
}
题意:
就是给你n个点,每个点有自己所在的层数。然后给你m条边,每条边有个花费。然后相邻层之间的点也可以互相移动,不过花费是k。问你从1号点走到n号点的最小花费。
思考:
1.很明显这个题也是一样,对于相邻的层的点要相互建边,如果暴力建边肯定也超时。所以也是两层之间建立虚点就可以了。但是提交发现还是超时?把存边的换成邻接表也不行。
2.然后我就怀疑存层数点的vector可能会超时,还有建的边太多?。如果我换种建图方式呢?对于每个点,他的虚点就是他的层数+n。这样最多只会n个虚点,而前一个是2n个虚点。对于每个点,让他自己的虚点连向自己的时候花费0,自己连上左右两个别人虚点的时候花费k。
3.这样总建立的边就3n个,加上本身给的2m个。也就是51e5个边,2*1e5个点。一定要算好内存,这种卡时间和内存的,尽量算好开最小。
代码:
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define ll long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const ll mod = 1e9+7,inf = 1e18;
const int N = 200010,M = 500100;
int T,n,m,k;
int va[N];
ll dist[N];
bool vis[N];
int h[N],e[M],ne[M],w[M],idx;
//h是点的个数,剩下的都是边的个数
void add(int a,int b,int c)
{
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void init()
{
idx = 0;
for(int i=0;i<=2*n;i++) h[i] = -1;
}
void distra()
{
for(int i=1;i<=2*n;i++) dist[i] = inf,vis[i] = 0;
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({
0,1});
dist[1] = 0;
while(q.size())
{
auto t = q.top();q.pop();
int now = t.se,dis = t.fi;
if(now==n) return ;
if(vis[now]) continue;
vis[now] = 1;
for(int i=h[now];i!=-1;i=ne[i])
{
int spot = e[i],x = w[i];
if(dist[spot]>dist[now]+x)
{
dist[spot] = dist[now]+x;
q.push({
dist[spot],spot});
}
}
}
}
signed main()
{
scanf("%d",&T);
for(int cs=1;cs<=T;cs++)
{
scanf("%d%d%d",&n,&m,&k);
init();
for(int i=1;i<=n;i++) scanf("%d",&va[i]);
for(int i=1;i<=n;i++) //让自己的虚点走向自己是0,自己走向别人的虚点是k
{
int now = va[i]+n;
int l = va[i]-1+n,r = va[i]+1+n;
add(now,i,0);
if(l>n) add(i,l,k); //如果这个虚点存在的话
if(r>n) add(i,r,k);
}
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
distra();
if(dist[n]==inf) dist[n] = -1;
printf("Case #%d: %lld\n",cs,dist[n]);
}
return 0;
}
总结:
多多总结。当出错的时候,考虑清楚,到底是哪里错了,多检查。多多积累经验。
边栏推荐
猜你喜欢
Gigabit 2 X light 8 electricity management industrial Ethernet switches WEB management - a key Ring Ring net switch
《nlp入门+实战:第八章:使用Pytorch实现手写数字识别》
深度学习——以CNN服装图像分类为例,探讨怎样评价神经网络模型
Based on the statistical QDirStat Qt directory
哎,又跟HR在小群吵了一架!
企业直播风起:目睹聚焦产品,微赞拥抱生态
KingbaseES数据库启动失败,报“内存段超过可用内存”
复现20字符短域名绕过
How to systematically plan and learn software testing?
十一种概率分布
随机推荐
Use serve to build a local server
db2中kettle报错 Field [XXX] is required and couldn‘t be found 解决方法
docker+网桥+redis主从+哨兵模式
FFmpeg —— 录制麦克风声音(附源码)
Hey, I had another fight with HR in the small group!
汇编语言之栈
移动支付线上线下支付场景
DIY电工维修如何拆卸和安装开关面板插座
pnpm 是凭什么对 npm 和 yarn 降维打击的
张量篇-应用案例
SQL注入中 #、 --+、 --%20、 %23是什么意思?
MRS: Alluxio的使用介绍
Take care of JVM performance optimization (own note version)
Basic form validation process
复制带随机指针的链表
Mobile payment online and offline payment scenarios
内网服务器访问远程服务器的端口映射
Introduction to mq application scenarios
【医保科普】维护医保基金安全,我们可以这样做
Enterprise live broadcast is on the rise: Witnessing focused products, micro-like embracing ecology