社区讨论
为什么80分,请求大佬帮助
P3761[TJOI2017] 城市参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lypqxkqz
- 此快照首次捕获于
- 2024/07/17 19:15 2 年前
- 此快照最后确认于
- 2024/07/17 20:05 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int n,pl,pr,maxn,ans=1e9;
int dis[10004],nowpre[10004];
int prer[10004],p[10004][10004];
vector<int> v[10004];
vector<int> w[10004];
int ww[5004][5004];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void dfs(int x,int fa,int cut,int ch){
if(cut==2&&ch==1) nowpre[x]=fa;
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
int z=w[x][i];
if(fa==y||p[x][y]) continue;
dis[y]=dis[x]+z;
if(maxn<dis[y]){
maxn=dis[y],pl=y;
}
dfs(y,x,cut,ch);
}
}
int getz(int x,int y){
pl=x;
for(int i=1;i<=2;i++){
maxn=0;
memset(dis,0,sizeof dis);
dfs(pl,0,i,y);
}
return maxn;
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int main(){
cin>>n;
for(int i=1;i<n;i++){
int a,b,c;cin>>a>>b>>c;
v[a].push_back(b);
v[b].push_back(a);
w[a].push_back(c);
w[b].push_back(c);
ww[a][b]=ww[b][a]=c;
}
getz(1,1);
for(int i=pl;i;i=nowpre[i]){
int x=i,y=nowpre[i];
if(y==0) continue;
p[x][y]=p[y][x]=1;
int lena=getz(x,0);
int lenb=getz(y,0);
ans=min(ans,max(max(lena,lenb),(lena+1)/2+(lenb+1)/2+ww[x][y]));
// cout<<x<<';'<<y<<' '<<lena<<' '<<lenb<<' '<<ww[x][y]<<endl;
// cout<<(lena+1)/2+(lenb+1)/2+ww[x][y]<<endl;
p[x][y]=p[y][x]=0;
}
cout<<ans+1;
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...