社区讨论
求助大佬,为什么此题要建立双向边
AT_abc138_d [ABC138D] Ki参与者 6已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @lo3781p6
- 此快照首次捕获于
- 2023/10/24 01:55 2 年前
- 此快照最后确认于
- 2023/10/24 01:55 2 年前
这是我用边表只建单向边的代码,在atcoder上大部分数据都过了,赛后的hack数据没过:
CPP#include<bits/stdc++.h>
using namespace std;
const int Maxn=2*1e5;
int n,q,t,v;
int to[Maxn<<1],head[Maxn<<1],net[Maxn],tot;
int pre[Maxn+10],val[Maxn];
int a,b;
void add(int u,int v)
{
to[++tot]=v;
net[tot]=head[u];
head[u]=tot;
}
void dfs(int now)
{
for(int i=head[now];i;i=net[i])
{
pre[to[i]]=val[to[i]]+pre[now];
dfs(to[i]);
}
}
int main()
{
cin>>n>>q;
for(int i=1;i<n;i++)
{
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=q;i++)
{
cin>>t>>v;
val[t]+=v;
}
pre[1]=val[1];
dfs(1);
for(int i=1;i<=n;i++)
cout<<pre[i]<<" ";
return 0;
}
这是vector建双向边的代码,ac了:
CPP#include<bits/stdc++.h>
using namespace std;
const int Maxn=2*1e5;
int n,q,t,v;
vector<int> a[Maxn<<1];
int pre[Maxn+10];
int aa,b;
void dfs(int now,int fa)
{
pre[now]+=pre[fa];
for(int i=0;i<a[now].size();i++)
if(a[now][i]!=fa)
dfs(a[now][i],now);
}
int main()
{
cin>>n>>q;
for(int i=1;i<n;i++)
{
cin>>aa>>b;
a[aa].push_back(b);
a[b].push_back(aa);
}
for(int i=1;i<=q;i++)
{
cin>>t>>v;
pre[t]+=v;
}
dfs(1,0);
for(int i=1;i<=n;i++)
cout<<pre[i]<<" ";
return 0;
}
是单向变和双向边的问题
还是边表和vector的问题呢???
求助大佬们
回复
共 10 条回复,欢迎继续交流。
正在加载回复...