Description
Once upon a time there was a strange kingdom, the kingdom had n cities which were connected by n directed roads and no isolated city.One day the king suddenly found that he can't get to some cities from some cities.How amazing!The king is petty so he won't build some new roads to improve this situation,but he has superpowers that he can change the direction of any road.To do this,he will gain a certain fatigue value for a certain road.The king didn't want to be too tired.So he want to know what is the smallest amount of fatigue value he will gain on the redirecting of roads so that from every city people can get to any other?
Input
The first line contains integer n (3<=n<=100) - amount of cities (and roads) in the king. 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 it costs ci.
Output
Output single integer - the smallest amount of fatigue value the king will gain on the redirecting of roads so that from every city people can get to any other.
Sample Input
3 1 3 1 1 2 1 3 2 1 3 1 3 1 1 2 5 3 2 1
Sample Output
1 2
看上去很难,稍加分析可知n个点n条边改变方向后可以连通,只有可能是一个环,所以我们判断反向边和正向边分别的权值总和取个小的就可以了.然后如果我们对每条单向边建一条负权值的反向边，跑一遍DFS就可以了.
#include <iostream> #include <algorithm> #include <string.h> #include <stdio.h> using namespace std; const int N = 105; int mp[N][N]; int vis[N]; int cost; int n,node; void dfs(int u,int pre){ if(vis[u]==1&&u!=1){ return; } vis[u]++; if(vis[u]==2&&u==1){ node = pre; return; } for(int i=1;i<=n;i++){ if(i==pre) continue; if(mp[u][i]&&!vis[i]){ if(mp[u][i]<0) cost+=mp[u][i]; dfs(i,u); } if(mp[u][i]&&vis[i]!=2&&i==1){ if(mp[u][i]<0) cost+=mp[u][i]; dfs(i,u); } } } int main() { while(scanf("%d",&n)!=EOF){ cost = 0; int sum = 0; memset(mp,0,sizeof(mp)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); mp[u][v] = w; sum+=w; mp[v][u] = -w; } dfs(1,-1); cost=-cost; printf("%d ",min(sum-cost,cost)); } return 0; }