比赛 20200109 评测结果 C
题目名称 树网的核 最终得分 0
用户昵称 数声风笛ovo 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2020-01-09 20:42:43
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
const int maxm=620;
const int inf=0x7fffffff;
struct EDGE{
	int u,v,w,next;
}s[maxm];
int first[maxn],num=0;
bool vis[maxn],inq[maxn],have[maxn];
int dis[maxn],start,end,pre[maxm],map[maxn][maxn];
int n,max_len;
queue<int> q;
inline void add(int u,int v,int w) {
	s[++num].next=first[u];
	first[u]=num;
	s[num].u=u;
	s[num].v=v;
	s[num].w=w;
}
inline int bfs(int S) {
	memset(pre,0,sizeof pre);
	memset(dis,0,sizeof dis);
	memset(have,0,sizeof have);
	q.push(S);inq[S]=true;dis[S]=0;have[S]=true;
	while(q.size()) {
		int u=q.front();q.pop();inq[u]=false;
		for(int i=first[u];i;i=s[i].next) {
			int v=s[i].v;
			if(have[v]) continue;
			if(dis[v]<dis[u]+s[i].w) {
				dis[v]=dis[u]+s[i].w;
				pre[v]=i;
				have[v]=true;
				if(!inq[v]) q.push(v),inq[v]=true;
			}
		}
	}
	int tmp1=dis[1],tmp2=1;
	for(int i=2;i<=n;i++) {
		if(tmp1<dis[i]) {
			tmp1=dis[i];
			tmp2=i;
		}
	}
	return tmp2;
}
inline void get_dtree() {
	start=bfs(1);
	end=bfs(start);
}
inline void floyd() {
	for(int k=1;k<=n;k++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
			}
		}
	}
}
inline int get_dmin() {
	int tmp=0,tmptmp=inf;
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {
			tmptmp=inf;
			for(int j=1;j<=n;j++) {
				if(vis[j]) tmptmp=min(tmptmp,map[i][j]);
			}
		}
		tmp=max(tmp,tmptmp);
	}
	return tmp;
}
int main() {
	freopen("core.in","r",stdin);
	freopen("core.out","w",stdout);
	scanf("%d%d",&n,&max_len);
	memset(map,0x3f,sizeof map);
	for(int i=1;i<n;i++) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
		map[a][b]=map[b][a]=c;
	}
	floyd();
	get_dtree();
	int len=0;
	for(int i=pre[end];s[i].u!=start;i=pre[s[i].u]) {
		len+=s[i].w;
		vis[s[i].u]=true;
	}vis[start]=true;vis[end]=true;
	for(int i=first[start];i;i=s[i].next) if(vis[s[i].v]) {len+=s[i].w;break;}
	int tmp1=start,tmp2=end,tmp1_len=0,tmp2_len=0;
	while(len>max_len) {
		for(int i=first[tmp1];i;i=s[i].next) {
			int v=s[i].v;
			if(vis[v]==true) {tmp1=v;tmp1_len=s[i].w;break;}
		}
		tmp2_len=s[pre[tmp2]].w;
		if(len-tmp1_len-tmp2_len>max_len) {
			len-=(tmp1_len+tmp2_len);
			vis[s[pre[tmp1]].u]=false;
			vis[tmp2]=false;
			tmp2=s[pre[tmp2]].u;
		}
		else if(len-tmp1_len>max_len && len-tmp2_len>max_len) {
			vis[s[pre[tmp1]].u]=false;
			vis[tmp2]=false;
			int d=get_dmin();
			printf("%d\n",d);
			return 0;
		}
		else {
			vis[s[pre[tmp1]].u]=false;
			int d1=get_dmin();
			vis[s[pre[tmp1]].u]=true;
			vis[tmp2]=false;
			int d2=get_dmin();
			printf("%d\n",min(d1,d2));
			return 0;
		}
	}
	int d=get_dmin();
	printf("%d\n",d);
	return 0;
}