1049

http://lightoj.com/volume_showproblem.php?problem=1049

题意是，在一副有向图中，要使得它变成一个首尾相连的图，需要的最小代价。

就是本来是1-->2  2-->3  1--->3的，变成1-->2-->3--->1的话，需要把1-->3变成3--->1，就要耗费这条边的代价

思路就是找出一个入度为2的点，要么往上走，要么往下走，dfs两次。

或者记录一个总和，dfs一次就好，上一次没耗费的，正是向下走要耗费的

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
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
", ++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;
}