1508

编程狂热爱好者 · 发表于 2024-3-25 20:32:36

#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 · 发表于 2024-3-25 21:12:44

我试试啊，看看能不能过

Michael · 发表于 2024-3-25 21:40:55

纯属参考：：

#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);
// int y=e[i].to;
// if(vis[y]) continue;
// d[y]=d[x]+1;
// dfs(y);
// if(d[c]<d[y])
// {
// d[c]=d[y];
// c=y;
// }
if(d[now]<d[i]) //自己填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);
dis[1].bian=1;//自己填2 也有可能是 dis[0].bian=0;
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;
//实在不知道怎么写了
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 · 发表于 2024-3-25 21:41:25

Michael · 发表于 2024-3-25 21:42:50

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

编程狂热爱好者 · 发表于 2024-3-27 18:36:08

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

1508

浏览过的版块