题目链接:https://ac.nowcoder.com/acm/contest/948/D
题意:
一个有向图,改动任意条边,问改动边的权值之和最小是多少?
分析:
把有向图建成特殊的无向图,正向时边的权值为0,反向权值为原来的权值,这样做是方便再搜索图的时候,没改动的边,花费为0,改动的花费对应的权值。
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 110;
struct node{
int v, w;
node(int x, int y) : v(x), w(y) {};
};
vector<node> G[N];
int n, ans;
void dfs(int u, int v, int w)
{
if(v == 1)
{
ans = min(ans, w);
return;
}
for(int i=0; i<G[v].size(); i++)
{
if(G[v][i].v == u) continue;
dfs(v, G[v][i].v, w + G[v][i].w);
}
}
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i=0; i<N; i++) G[i].clear();
for(int i=0; i<n; i++)
{
int u, v, w; // u->v有一条权值w的有向边
scanf("%d %d %d", &u, &v, &w);
G[u].push_back(node(v, 0)); // 正向设为0
G[v].push_back(node(u, w)); // 反向设为W
}
ans = INF;
for(int i=0; i<G[1].size(); i++)
{
dfs(1, G[1][i].v, G[1][i].w);
}
printf("%d\n", ans);
}
return 0;
}