题解 | #B题#

思路

看作无向图的时候，它是一个环，因此遍历每个点只有顺时针和逆时针两种。 所以先跑一次无向图的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;
}