1508

编程狂热爱好者

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,pass[305],from,lu[305],ge,dp[305],minn=1E18,s,ma[305][305],qian[305];
bool vis[305],t[305];
struct node{
    int di,bian;
}dis[10005];
void dfs(int now){
    vis[now]=true;
    for(int i=1;i<=n;i++){
            if(ma[now][i]==-1||vis[i]||t[i]==1)continue;
            if(dis[now].di==-2)dis[now].di=0;
        dfs(i);
        if(自己填1){
                        dis[now].di=dis[i].di+ma[now][i],dis[now].bian=dis[i].bian;
                        if(from)pass[now]=i;
                }
    }
}
void print(int now){
        if(now){
                print(pass[now]);
                lu[++ge]=now;
                if(ge!=1)qian[ge]=qian[ge-1]+ma[lu[ge-1]][lu[ge]];
        }
}
signed main(){
        memset(ma,-1,sizeof(ma));
    cin>>n>>s;
    for(int i=1;i<n;i++){
            dis[i].bian=i;
            int u,v,w;
        cin>>u>>v>>w;
        ma[u][v]=w;
        ma[v][u]=w;
    }
    dis[n].bian=n;
    dfs(1);
    自己填2
    dfs(from);
        print(from);
        for(int i=1;i<=ge;i++){
                for(int j=i;j<=ge;j++){
                        if(qian[j]-qian[i]>s)break;
                        自己填3
                        int maxx=-1;
                        for(int l=1;l<=ge;l++)
                                if(t[lu[l]]==1){
                                    for(int i=1;i<=n;i++)vis[i]=false,dis[i].di=0,dis[i].bian=i;
                                    dis[lu[i]].di=-2;
                                        dfs(lu[l]);
                                        maxx=max(maxx,dis[lu[l]].di);
                                }
                        minn=min(minn,maxx);
                }
                memset(t,false,sizeof(t));
        }
        cout<<minn;
}

Michael

我试试啊，看看能不能过

Michael

纯属参考：：

1. 
   
2. #include<bits/stdc++.h>
   
3. #define int long long
   
4. using namespace std;
   
5. int n,ans,pass[305],from,lu[305],ge,dp[305],minn=1E18,s,ma[305][305],qian[305];
   
6. bool vis[305],t[305];
   
7. struct node{
   
8.     int di,bian;
   
9. }dis[10005];
   
10. void dfs(int now){
    
11.     vis[now]=true;
    
12.     for(int i=1;i<=n;i++){
    
13.         if(ma[now][i]==-1||vis[i]||t[i]==1)continue;
    
14.         if(dis[now].di==-2)dis[now].di=0;
    
15.         dfs(i);
    
16.         
    
17.         // int y=e[i].to;
    
18.         // if(vis[y]) continue;
    
19.         // d[y]=d[x]+1;
    
20.         // dfs(y);
    
21.         // if(d[c]<d[y])
    
22.         // {
    
23.         //     d[c]=d[y];
    
24.         //     c=y;
    
25.         // }
    
26.         
    
27.         if(d[now]<d[i])  //自己填1    （应该没什么问题吧）
    
28.         {
    
29.             dis[now].di=dis[i].di+ma[now][i],dis[now].bian=dis[i].bian;
    
30.             if(from) pass[now]=i;
    
31.         }
    
32.     }
    
33. }
    
34. void print(int now)
    
35. {
    
36.     if(now)
    
37.     {
    
38.         print(pass[now]);
    
39.         lu[++ge]=now;
    
40.         if(ge!=1)
    
41.         {
    
42.             qian[ge]=qian[ge-1]+ma[lu[ge-1]][lu[ge]];
    
43.         }
    
44.     }
    
45. }
    
46. signed main()
    
47. {
    
48.     memset(ma,-1,sizeof(ma));
    
49.     cin>>n>>s;
    
50.     for(int i=1;i<n;i++)
    
51.     {
    
52.         dis[i].bian=i;
    
53.         int u,v,w;
    
54.         cin>>u>>v>>w;
    
55.         ma[u][v]=w;
    
56.         ma[v][u]=w;
    
57.     }
    
58.     dis[n].bian=n;
    
59.     dfs(1);
    
60.     dis[1].bian=1;//自己填2   也有可能是 dis[0].bian=0;
    
61.     dfs(from);
    
62.     print(from);
    
63.     for(int i=1;i<=ge;i++)
    
64.     {
    
65.         for(int j=i;j<=ge;j++)
    
66.         {
    
67.             if(qian[j]-qian[i]>s) break;
    
68.             
    
69.             //实在不知道怎么写了
    
70.             
    
71.             int maxx=-1;
    
72.             for(int l=1;l<=ge;l++)
    
73.             {
    
74.                 if(t[lu[l]]==1)
    
75.                 {
    
76.                     for(int i=1;i<=n;i++)
    
77.                     {
    
78.                         vis[i]=false;
    
79.                         dis[i].di=0;
    
80.                         dis[i].bian=i;
    
81.                     }
    
82.                     dis[lu[i]].di=-2;
    
83.                     dfs(lu[l]);
    
84.                     maxx=max(maxx,dis[lu[l]].di);
    
85.                 }
    
86.                 minn=min(minn,maxx);
    
87.             }
    
88.             memset(t,false,sizeof(t));
    
89.         }
    
90.         
    
91.     }
    
92.     cout<<minn;
    
93. }
    
94. 
    

复制代码

Michael

Michael

@编程狂热爱好者，你的（自己填3）好难想啊
真无语

编程狂热爱好者

提示一下，1号是在求最长的路径，2号是初始化，3号是标记这个点是否在枚举范围之内