算法1(姑且叫他floyd吧)
一开始以为是树的重心那题变过来的,后面发现是想多了,dp?floyd好像也是耶。让我浅试一哈没想到过了,这不就是每个边权为1嘛,然后最后全部枚举一下找出最小值不就ok啦。
#include<bits/stdc++.h>
using namespace std;
const int N = 110,INF = 0x3f3f3f3f;
int n;
int cnt[N];
int f[N][N];
int main()
{
cin>>n;
memset(f,INF,sizeof f);
for(int i=1;i<=n;i++)
{
f[i][i]=0;
int l,r;
cin>>cnt[i]>>l>>r;
if(l) f[l][i]=f[i][l]=1;
if(r) f[r][i]=f[i][r]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
int res=INF;
for(int i=1;i<=n;i++)
{
int sum=0;
for(int j=1;j<=n;j++)
{
sum+=f[i][j]*cnt[j];
}
res=min(res,sum);
}
cout<<res<<endl;
return 0;
}
算法2(佬的dfs爆搜)
也是全部枚举一遍,用dfs找出最小的那个。 搬自该位大佬
#include<bits/stdc++.h>
using namespace std;
const int N = 110,M = N*2,INF = 0x3f3f3f3f;
int n;
int cnt[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u,int father,int d)
{
int sum=d*cnt[u];
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==father) continue;
sum+=dfs(j,u,d+1);
}
return sum;
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
int l,r;
cin>>cnt[i]>>l>>r;
if(l) add(i,l),add(l,i);
if(r) add(i,r),add(r,i);
}
int res=INF;
for(int i=1;i<=n;i++) res=min(res,dfs(i,-1,0));
cout<<res<<endl;
return 0;
}