比赛 |
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;
}