本文共 1882 字，大约阅读时间需要 6 分钟。
题意是，在一副有向图中，要使得它变成一个首尾相连的图，需要的最小代价。
就是本来是1-->2 2-->3 1--->3的，变成1-->2-->3--->1的话，需要把1-->3变成3--->1，就要耗费这条边的代价
思路就是找出一个入度为2的点，要么往上走，要么往下走，dfs两次。
或者记录一个总和，dfs一次就好，上一次没耗费的，正是向下走要耗费的
#include #include #include #include #include #include #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include #include #include #include #include #include #include #include const int maxn = 100 + 20;struct node { int u, v, w, tonext; bool flag;} e[maxn * 2];int first[maxn];int num;int in[maxn];int DFN;void add(int u, int v, int w, bool flag) { ++num; e[num].u = u; e[num].v = v; e[num].w = w; e[num].tonext = first[u]; first[u] = num; e[num].flag = flag;}int now;int dfs(int cur, int root, int fa) { if (cur == root && now == 0) return 0; if (cur == root) { for (int i = first[cur]; i; i = e[i].tonext) { now--; if (now == 0) { return e[i].w + dfs(e[i].v, root, cur); } } } else { for (int i = first[cur]; i; i = e[i].tonext) { int v = e[i].v; if (v == fa) continue; if (e[i].flag) { return dfs(v, root, cur); } else { return e[i].w + dfs(v, root, cur); } } }}void work() { num = 0; ++DFN; int n; scanf("%d", &n); int root = -inf; for (int i = 1; i <= n; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); if (in[v] == DFN) { root = v; } in[v] = DFN; add(u, v, w, true); add(v, u, w, false); } int ans = inf; if (root == -inf) { ans = 0; } else { now = 1; ans = dfs(root, root, 0); now = 2; ans = min(ans, dfs(root, root, 0)); } static int f = 0; printf("Case %d: %d\n", ++f, ans);}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif int t; scanf("%d", &t); while (t--) work(); return 0;}
转载于:https://www.cnblogs.com/liuweimingcprogram/p/6421521.html
