水贴!
2024-02-22 17:15:28
发布于:浙江
小埋的农场设置
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,w[N],res,ans=0x3f3f3f3f;
void dfs(int u,vector<vector<int>> &v,vector<bool> &vis,int step){
res+=w[u]*step;
for(auto it : v[u]){
if(vis[it]) continue;
vis[it]=1;
dfs(it,v,vis,step+1);
}
}
int main(){
cin>>n;
vector<vector<int>>v(n+1);
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
vector<bool> vis(n+1);
vis[i]=1;
res=0;
dfs(i,v,vis,0);
ans=min(ans,res);
}
cout<<ans;
return 0;
}
小埋学习图之环问题
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int dis[10005];
vector <int> v[10005];
int ans=0x3f3f3f3f;
void dfs(int u,int fa,int res){
for(auto it : v[u]){
if(it==fa) continue;
if(dis[it]!=-1){
ans=min(ans,abs(res-dis[it])+1);
continue;
}
dis[it]=res+1;
dfs(it,u,res+1);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
memset(dis,-1,sizeof(dis));
dis[i]=1;
dfs(i,-1,1);
}
if(ans==0x3f3f3f3f) ans=-1;
cout<<ans;
return 0;
}
这里空空如也
有帮助,赞一个