社区讨论

为什么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 条回复,欢迎继续交流。

正在加载回复...