题目链接

题意

求有向图的最小生成树，且根不定。

思路

最小树形图即求有向图的最小生成树，用的是朱刘算法。

这里不定根，那么可以建立一个虚根，让虚根和所有点相连，权值为一个很大的数（这里直接设为所有边之和+1）。

如果最后的答案比两倍的sum还大，就说明至少有两个点是通过虚边（从虚点走出去的边）相连（因为虚边的边权很大），那么这也是一个不连通的图。

找真正的根的话，只要找和虚根相连并且走过虚边的点就是了。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 11;

const int INF = 0x3f3f3f3f;

typedef long long LL;

struct Edge {

    int u, v; LL w;

} edge[N*2];

int tot, n, m, minroot;

int pre[N], id[N], vis[N];

LL in[N];

void Add(int u, int v, LL w) {

    edge[tot++] = (Edge) { u, v, w };

}

LL zhuliu(int root, int n, int m) {

    LL ans = 0;

    int u, v; LL w;

    while(true) {

        for(int i = 0; i < n; i++) in[i] = 1e17;

        for(int i = 0; i < m; i++) { // 找最小入边

            u = edge[i].u, v = edge[i].v, w = edge[i].w;

            if(u != v && w < in[v]) pre[v] = u, in[v] = w,

                                    minroot = (u == root ? i : minroot); // 只有这里找根和模板不一样

        }

        for(int i = 0; i < n; i++) // 存在孤立点

            if(i != root && in[i] == 1e17) return -1;

        int tn = 0;

        memset(id, -1, sizeof(id));

        memset(vis, -1, sizeof(vis));

        in[root] = 0;

        for(int i = 0; i < n; i++) { // 找环

            ans += in[i];

            v = i;

            while(vis[v] != i && id[v] == -1 && v != root)

                vis[v] = i, v = pre[v];

            if(v != root && id[v] == -1) { // 重新标号

                for(u = pre[v]; u != v; u = pre[u]) id[u] = tn;

                id[v] = tn++;

            }

        }

        if(tn == 0) break; // 不存在环

        for(int i = 0; i < n; i++) // 重新标号

            if(id[i] == -1) id[i] = tn++;

        for(int i = 0; i < m; i++) { // 更新其他点到环的距离

            u = edge[i].u, v = edge[i].v;

            edge[i].u = id[u];

            edge[i].v = id[v];

            if(edge[i].u != edge[i].v)

                edge[i].w -= in[v];

        }

        n = tn;

        root = id[root];

    }

    return ans;

}

int main() {

//    freopen("in.txt", "r", stdin);

//    freopen("out.txt", "w", stdout);

    while(~scanf("%d%d", &n, &m)) {

        tot = 0; LL sum = 0;

        for(int i = 0; i < m; i++) {

            int u, v; LL w;

            scanf("%d%d%lld", &u, &v, &w);

            Add(u, v, w); sum += w;

        }

        sum++;

        for(int i = 0; i < n; i++)

            Add(n, i, sum);

        LL ans = zhuliu(n, n + 1, tot); // 虚根为n

//        printf("ans : %lld\n", ans);

        if(ans == -1 || ans >= 2 * sum) puts("impossible");

        else printf("%lld %d\n", ans - sum, minroot - m);

        puts("");

    }

    return 0;

}