B - Ring road
CodeForces - 24A
Nowadays the one-way traffic is introduced all over the world in order to improve driving safety and reduce traffic jams. The government of Berland decided to keep up with new trends. Formerly all n cities of Berland were connected by n two-way roads in the ring, i. e. each city was connected directly to exactly two other cities, and from each city it was possible to get to any other city. Government of Berland introduced one-way traffic on all n roads, but it soon became clear that it's impossible to get from some of the cities to some others. Now for each road is known in which direction the traffic is directed at it, and the cost of redirecting the traffic. What is the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other?
Input
The first line contains integer n (3 ≤ n ≤ 100) — amount of cities (and roads) in Berland. Next n lines contain description of roads. Each road is described by three integers ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) — road is directed from city ai to city bi, redirecting the traffic costs ci.
Output
Output single integer — the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other.
Example
Input
3
1 3 1
1 2 1
3 2 1
Output
1
Input
3
1 3 1
1 2 5
3 2 1
Output
2
Input
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42
Output
39
Input
4
1 2 9
2 3 8
3 4 7
4 1 5
Output
0
题意：已知结点与有向边构成一个环，将环中一些边的方向调转使环从一个结点出发能够回到此结点，每一个边有自己的权值，问怎么改变使权值加和最小，输出最小的权值加和。
解法：用a[i][j]表示i与j之间的边，初始值设为-1，如果i和j之间有边，若方向从i到j则a[j][i]=value,a[i][j]=0，dfs，从一个结点x向一个方向搜，如果a[x][i]!=-1，sum+=a[i]，回到起始结点递归结束，此时sum为一个方向的权值之和，有权值总和减去sum为另一方向权值之和，取两者最小值输出。
代码：
#include<iostream>
#include<cstring>
using namespace std;
int a[105][105];
int n,sum=0,flag=0;
void dfs(int x,int pre)
{
for(int i=1;i<=n;i++){
if(a[x][i]!=-1&&i!=pre){
sum+=a[x][i];
if(i==1){
flag=1;
break;
}
dfs(i,x);
}
if(flag==1)
break;
}
}
int main()
{
cin>>n;
int x,y,z,s=0;
memset(a,-1,sizeof(a));
for(int i=1;i<=n;i++){
cin>>x>>y>>z;
a[x][y]=0;
a[y][x]=z;
s+=z;
}
dfs(1,-1);
cout<<min(sum,s-sum)<<endl;
}
