社区讨论
AC了但是有一个小小的疑问,求大佬解答
P3304[SDOI2013] 直径参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mhjidajf
- 此快照首次捕获于
- 2025/11/04 03:03 4 个月前
- 此快照最后确认于
- 2025/11/04 03:03 4 个月前
这是AC代码:
CPP**#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n,dep[N],l,r,f[N],maxx,length[N],ll[N],rr[N],ww[N],a[N],cnt,cnt1,maxdep;
bool vis[N];
vector<pair<int,int> > g[N];
void dfs (int u,int fa) {
f[u] = fa;
for (auto e : g[u]) {
int v = e.first;
int w = e.second;
if (v == fa) continue;
ww[v] = w;
dep[v] = dep[u] + w;
dfs (v,u);
}
if (dep[u] > maxx) {
maxx = dep[u];
r = u;
}
}
void dfs1 (int u,int fa) {
for (auto e: g[u]) {
int v = e.first;
int w = e.second;
if (v == fa || vis[v] == true) continue;
dep[v] = dep[u] + w;
dfs1 (v,u);
}
if (dep[u] > maxdep) {
maxdep = dep[u];
}
}
signed main () {
cin >> n;
for (int i = 1;i <= n - 1;i ++) {
int a,b,c;
cin >> a >> b >> c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
dfs (1,-1);
l = r;
dep[r] = 0;
maxx = 0;
dfs (r,-1);
vis[l] = vis[r] = true;
int disl = maxx,disr = 0;
int id = r;
cnt = 0;
while (id != l) {
vis[id] = true;
disl -= ww[id];
ll[cnt] = disl;
disr += ww[id];
rr[cnt] = disr;
id = f[id];
a[cnt] = id;
++ cnt;
}
for (int i = 0;i < cnt;i ++) {
dep[a[i]] = 0;
dfs1 (a[i],-1);
length[a[i]] = maxdep;
maxdep = 0;
}
int rend = cnt - 1,lfirst = 0;
for (int i = 0;i < cnt;i ++) {
if (length[a[i]] == rr[i]) rend = i;
if (length[a[i]] == ll[i]) {
lfirst = i;
break;
}
}
cout << maxx << '\n' << lfirst - rend << '\n';
return 0;
}
这是我的代码:
CPP#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n,dep[N],l,r,f[N],maxx,length[N],ll[N],rr[N],ww[N],a[N],cnt,cnt1,maxdep;
bool vis[N];
vector<pair<int,int> > g[N];
void dfs (int u,int fa) {
f[u] = fa;
for (auto e : g[u]) {
int v = e.first;
int w = e.second;
if (v == fa) continue;
ww[v] = w;
dep[v] = dep[u] + w;
dfs (v,u);
}
if (dep[u] > maxx) {
maxx = dep[u];
r = u;
}
}
void dfs1 (int u,int fa) {
for (auto e: g[u]) {
int v = e.first;
int w = e.second;
if (v == fa || vis[v] == true) continue;
dep[v] = dep[u] + w;
dfs1 (v,u);
}
if (dep[u] > maxdep) {
maxdep = dep[u];
}
}
signed main () {
cin >> n;
for (int i = 1;i <= n - 1;i ++) {
int a,b,c;
cin >> a >> b >> c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
dfs (1,-1);
l = r;
dep[r] = 0;
// maxx = 0; 这里没有给maxx清零,然后WA了67两个点,但第二遍dfs求得长度不是一定会比第一遍大于或者等于吗,这样不就更新了吗,为什么要清空啊。
dfs (r,-1);
vis[l] = vis[r] = true;
int disl = maxx,disr = 0;
int id = r;
cnt = 0;
while (id != l) {
vis[id] = true;
disl -= ww[id];
ll[cnt] = disl;
disr += ww[id];
rr[cnt] = disr;
id = f[id];
a[cnt] = id;
++ cnt;
}
for (int i = 0;i < cnt;i ++) {
dep[a[i]] = 0;
dfs1 (a[i],-1);
length[a[i]] = maxdep;
maxdep = 0;
}
int rend = cnt - 1,lfirst = 0;
for (int i = 0;i < cnt;i ++) {
if (length[a[i]] == rr[i]) rend = i;
if (length[a[i]] == ll[i]) {
lfirst = i;
break;
}
}
cout << maxx << '\n' << lfirst - rend << '\n';
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...