HDU 2121 Ice-cream's world II(Minimum tree-shape graph)

Description

N个点(0~N-1)M条有向边，不定根(任意一点可选做根节点)求最小树形图

Anlyze

增加一个超级节点”伪根“，连向每一个点。

关于这些边的权值：

①最初想的是像最短路题目似的，将超点连向各点的边的权值设为0，最后得出的最短路长度就直接是答案。后来想想不对，朱刘算法第一步找“最小入边集”，那样选出来的最小入边集就是这新增的N条边了。

②所以为了不影响寻找正常的最小入边集，这新增的N条边的权值应该比最小入边集里所有边的长度都要大，假设最小入边集中最长边长度为X，那这N条新边权值要设为 >= X的一个数。

③那样做还要先求一遍最小入边集，干脆放大一下，找原图所有边中的最长边，设为Y，那么这N条新边的边权要 >= Y;

④还有个问题，我在求最小树形图时，用了两条“新边”（理论上应该只用一条：u=伪根，v=真根の那条边），后期无法鉴别。而倘若我直接把“新边”边权设为sum(原图所有边的边权和)，最后答案小于2倍的sum才算真正找到了最小树形图。

所以说N条新边的边权应 >= sum，最后记得从答案里减掉一个新边边权。

关于寻找“真根”：

理论上来说，在选最小入边集时，我们记录了每个点的前驱，if(u == 伪根) 则v == 真根。但还要“缩点”，“缩点”会使所有点的下标屡次改变，这时记录的点就无意义了。

但是，我们是按顺序添加新边的，比如某条新边下标为m + x,它从伪根指向节点x，那么即使后来缩点了，那唯一一条连接伪根与真根的边，它的u、v都变了，但下边没变，那么那条边依然是独一无二的(它曾指向“真根”，证据就是它的下标 - m == 真根)。(事实上每条边都是独一无二的）

5 5
4 3 1
3 1 2
1 4 3
1 2 1
2 0 1

///1.Set of in
for(int i = 0; i < n; ++i)
    in[i] = -1;
for(int i = 1; i <= m; ++i)
    if(e[i].u != e[i].v && (e[i].w < in[ e[i].v ] || in[ e[i].v ] < 0))
    {
        in[ e[i].v ] = e[i].w, pre[ e[i].v ] = e[i].u;
        if(e[i].u == root)
        {
            cout << i << ' ' << e[i].u << ' ' << e[i].v << '\n';
            start = i;
        }
    }

理解第一个if的第二个条件，在缩点后的意义:选取环上最长边的终点v作为此环的“进入点”

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f;

int n, m, id[N], pre[N], vis[N], in[N], start;

struct edge
{
    int u, v, w;
}e[10 * N + N];///Pay attention to the number of edges!

int zhuliu(int root)
{
    int u, v, res = 0;
    while(true)
    {
        ///1.Set of in
        for(int i = 0; i < n; ++i)
            in[i] = -1;
        for(int i = 1; i <= m; ++i)
            if(e[i].u != e[i].v && (e[i].w < in[ e[i].v ] || in[ e[i].v ] < 0))
            {
                in[ e[i].v ] = e[i].w, pre[ e[i].v ] = e[i].u;
                if(e[i].u == root)
                    start = i;
            }
        for(int i = 0; i < n; ++i)
            if(i != root && in[i] < 0)
                return -1;

        ///2.Directed circle
        int cnt = 0;
        memset(id, -1, sizeof(id));
        memset(vis,-1, sizeof(vis));
        in[root] = 0;
        for(int i = 0; i < n; ++i)
        {
            res += in[i];
            v = i;
            while(id[v] == -1 && v != root && vis[v] != i)
                vis[v] = i, v = pre[v];
            if(id[v] == -1 && v != root)///   vis[v] == i
            {
                for(u = pre[v]; u != v; u = pre[u])
                    id[u] = cnt;
                id[v] = cnt++;
            }
        }

        ///3.No circle -> Over
        if(cnt == 0)
            break;

        ///4.Process other nodes ,and then "shrink".
        for(int i = 0; i < n; ++i)
            if(id[i] == -1)
                id[i] = cnt++;
        for(int i = 1; i <= m; ++i)
        {
            v = e[i].v;
            e[i].u = id[ e[i].u ];
            e[i].v = id[ e[i].v ];
            if(e[i].u != e[i].v)
                e[i].w -= in[v];///This v is the original v!
        }
        n = cnt;
        root = id[root];
    }
    return res;
}

int main()
{
    while(~scanf("%d %d", &n, &m))
    {
        int u, v, w, tn = n, tm = m, sum = 0;
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d %d %d", &u, &v, &w);
            e[i].u = u, e[i].v = v, e[i].w = w;
            sum += w;
        }
        for(int i = 0; i < n; ++i)
        {
            e[m + i + 1].u = n;
            e[m + i + 1].v = i;
            e[m + i + 1].w = sum + 1;
        }
        m += n, n++;///Pay attention to the order!
        int ans = zhuliu(tn);
        if(ans < 0 || ans >= 2 * (sum + 1))
            cout << "impossible" << '\n' << '\n' ;
        else
            printf("%d %d\n\n", ans - (sum + 1), start - tm - 1);
    }
    return 0;
}