求助!第二个样例总是过不了。路过的神犇帮帮忙。
查看原帖
求助!第二个样例总是过不了。路过的神犇帮帮忙。
28088
钱逸凡楼主2018/6/13 23:20

我觉得我的思路没问题啊

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
struct Node{
    int v;
    int next;
    int val;
}node[2020];
int dist[2020][2020];
int find__f[1010][1010];
int vis[1010][1050];
int maxn;
int n,s,f;
queue<int>q;
int inque[1010];
int top,head[1010];
inline void addedge(int u,int v,int val){
    node[++top].v=v;
    node[top].val=val;
    node[top].next=head[u];
    head[u]=top;
}
inline int max(int a,int b){
    return a>b?a:b;
}
inline int min(int a,int b){
    return a<b?a:b;
}
void spfa(int st){
    dist[st][st]=0;
    q.push(st);
    int u,i,d;
    while(!q.empty()){
    u=q.front();
    inque[u]=0;
    q.pop();
    for(i=head[u];i;i=node[i].next){
    d=node[i].v;
    if(dist[st][d]>dist[st][u]+node[i].val){
    dist[st][d]=node[i].val+dist[st][u];	
	maxn=max(maxn,dist[st][d]);
    if(inque[d]==0){
        q.push(d);	
        inque[d]=1;
}
    }
    }
    }
}
int find_f(int i,int j){
    if(find__f[i][j]!=0)return find__f[i][j];
	int ma=0;
    for(int k=1;k<=n;k++){
        ma=max(ma,(dist[i][k]+dist[k][j]-dist[i][j])/2);
    }
    return find__f[i][j]=find__f[j][i]=ma;
}//以i,j为树网的核,找偏心距
void dfs1(int i,int j,int o){
	if(vis[i][o]!=0)return;
	vis[i][o]=1;
	if(i==j)return;
	for(int k=head[i];k;k=node[k].next){
		int d=node[k].v;
		if(dist[i][k]+dist[k][j]==dist[i][j]){
			dfs1(d,j,o);
			break;
		}
	}
}//找出所有第o条直径上的点 
int main(){
	freopen("cin.txt","r",stdin);
    memset(dist,0x7f,sizeof(dist));
    n=Read(),s=Read();
    f=1<<30;
    register int i,j,k;
    int a,b,val;
    for(i=1;i<n;i++){
    a=Read(),b=Read(),val=Read();
    addedge(a,b,val);
    addedge(b,a,val);
    }
    int o=0;
    maxn=0;
    for(i=1;i<=n;i++)spfa(i);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(dist[i][j]==maxn){//找直径
            dfs1(i,j,++o);
            }
        }
    }
    for(k=1;k<=o;k++){	
	for(i=1;i<=n;i++){
    		for(j=1;j<=n;j++){
	   			if(vis[i][k]==1&&vis[j][k]==1&&dist[i][j]<=s){
    				f=min(f,find_f(i,j));
				} 
			}
		} 
	}
    printf("%d",f);
    return 0;
}
2018/6/13 23:20
加载中...