Ice_cream’s world II - HDU 2121 - 最小树形图

题目

  http://acm.hdu.edu.cn/showproblem.php?pid=2121

题意

  给你n个点和m条有向边，问最少能花费多少将它们连起来，如果能连起来输出需要的权值和根的序号，不能的话输出impossible。

思路

  不定根最小树形图，虚拟出一个树根出来，令这个树根到每个点的权值为大于所有边的权值之和sum，在这里我令其到各点的权值为sum+1，最后如果存在最小树形图的话在输出权值的时候减去sum+1就可以了。此时所对应的树根就是和虚拟树根相连的那个点。

实现

  在写题的过程中WA了很多遍，检查来检查去没有发现问题。后来试了一组有环的数据发现权值没问题，根错了。

  原来是在定根的时候，我一开始的思路是pos = v-1，然后在输出的时候就直接printf一下pos，在无环也就是不需要更新图的时候这样的确是对的，但是一旦图被更新，这样一来点和点之间的对应关系就错了。

  所以正确的方法应该是通过edge的下标减去边数m来确定，也就是pos = i，然后在输出的时候printf("%lld %d\n", ans - sum, pos - m);

代码

//
//  main.cpp
//  L
//
//  Created by LucienShui on 2017/5/11.
//  Copyright © 2017年 LucienShui. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#define memset(a,b) memset(a,b,sizeof(a))
#define ull unsigned long long
#define ll long long

using namespace std;

#define maxn 1008

struct {
    int u,v;
    ll w;
}edge[maxn*20];

int n, m, tmp, pos, pre[maxn], vis[maxn], id[maxn];
ll sum, in[maxn];
const int INF = 0x3f3f3f3f;

ll directed_MST(int root, int n, int m) {
    ll ans = 0;
    while(true) {
        for (int i = 0; i < n; i++) in[i] = INF;
        for (int i = 0; i < m; i++) {
            int u = edge[i].u, v = edge[i].v;
            if (u != v && edge[i].w < in[v]) {
                in[v] = edge[i].w;
                pre[v] = u;
                if (u == root) {
                    pos = i;/*pos = v-1*/
                }
            }
        }
        for(int i=0 ; i<n ; i++)
            if (in[i] == INF && i!=root) return -1;
        int cnt = 0;
        memset(id,-1);
        memset(vis,-1);
        in[root] = 0;
        for(int i=0 ; i<n ; i++) {
            ans += in[i];
            int v = i;
            while(vis[v] != i && id[v] == -1 && v!=root) {
                vis[v] = i;
                v = pre[v];
            }
            if(v != root && id[v] == -1) {
                for(int u = pre[v] ; u!=v ; u = pre[u])
                    id[u] = cnt;
                id[v] = cnt++;
            }
        }
        if(cnt == 0) break;
        for(int i=0 ; i<n ; i++) if(id[i] == -1) id[i] = cnt++;
        for(int i=0 ; i<m ; i++) {
            int v = edge[i].v;
            edge[i].u = id[edge[i].u];
            edge[i].v = id[edge[i].v];
            if(edge[i].u != edge[i].v) edge[i].w -= in[v];
        }
        n = cnt;
        root = id[root];
    }
    return ans;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("/home/lucienshui/Desktop/in", "r", stdin);
#endif
    while(~scanf("%d%d", &n, &m)) {
        sum = 0;
        for(int i=0 ; i<m ; i++) {
            scanf("%d%d%lld", &edge[i].u, &edge[i].v, &edge[i].w);
            edge[i].u++, edge[i].v++;
            sum += edge[i].w;
        }
        sum++, tmp = m;
        for(int i=1 ; i<=n ; i++) {
            edge[tmp].u = 0;
            edge[tmp].v = i;
            edge[tmp++].w = sum;
        }
        ll ans = directed_MST(0,n+1,m+n);
        if(ans == -1 || ans - sum >= sum) puts("impossible");
        else printf("%lld %d\n", ans - sum, pos - m);
        putchar('\n');
    }
    return 0;
}