思路
看作无向图的时候,它是一个环,因此遍历每个点只有顺时针和逆时针两种。 所以先跑一次无向图的dfs确定顺序,然后在有向边的时候如果方向不对就加上其权值,得 到修改代价,答案取一个min就可以了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,u,v,w,mp[N][N],vis[N],dfn[N],idx=0;
vector<int>G[N];
void dfs(int x){
vis[x]=1;
dfn[++idx]=x;
for(auto to:G[x]){
if(vis[to]) continue;
dfs(to);
}
}
void clear(){
idx=0;
memset(vis,0,sizeof(vis));
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;i++) G[i].clear();
}
signed main(){
while(cin>>n){
for(int i=1;i<=n;i++){
cin>>u>>v>>w;
mp[u][v]=w;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1);
int ans1=0,ans2=0;
for(int i=1;i<n;i++) ans1+=mp[dfn[i]][dfn[i+1]];
ans1+=mp[dfn[n]][dfn[1]];
for(int i=n;i>1;i--) ans2+=mp[dfn[i]][dfn[i-1]];
ans2+=mp[dfn[1]][dfn[n]];
cout<<min(ans1,ans2)<<"\n";
clear();
}
return 0;
}