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
題意：已知結(jié)點(diǎn)與有向邊構(gòu)成一個(gè)環(huán)，將環(huán)中一些邊的方向調(diào)轉(zhuǎn)使環(huán)從一個(gè)結(jié)點(diǎn)出發(fā)能夠回到此結(jié)點(diǎn)搔课，每一個(gè)邊有自己的權(quán)值胰柑，問怎么改變使權(quán)值加和最小，輸出最小的權(quán)值加和爬泥。
解法：用a[i][j]表示i與j之間的邊柬讨，初始值設(shè)為-1，如果i和j之間有邊袍啡，若方向從i到j(luò)則a[j][i]=value,a[i][j]=0踩官，dfs，從一個(gè)結(jié)點(diǎn)x向一個(gè)方向搜境输，如果a[x][i]!=-1蔗牡，sum+=a[i]，回到起始結(jié)點(diǎn)遞歸結(jié)束畴嘶，此時(shí)sum為一個(gè)方向的權(quán)值之和蛋逾，有權(quán)值總和減去sum為另一方向權(quán)值之和，取兩者最小值輸出窗悯。
代碼：
#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;
}
