HDU-2121（有向图最小生成树，朱刘算法）

Ice_cream’s world II

题意：给定一个有向图，求最小生成树是否存在，若存在则求出根节点以及最小权值。

思路：利用朱刘算法，

1. 求最短弧集合E0
2. 检查E0
3. 收缩G中的有向环
4. 展开收缩点

（以下代码节点下标从 0 0 0开始）

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh
")
#define see(x) (cerr<<(#x)<<=<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<ll,int> pr;
inline int read() {int x=0;char c=getchar();while(c<0||c>9)c=getchar();while(c>=0&&c<=9)x=x*10+c-0,c=getchar();return x;}

const int maxn = 1e3+10;
const int mod = 1e9+7;
const double eps = 1e-7;
const int INF = 2e9;

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

int pre[maxn], id[maxn], vis[maxn], n, m, pos;
ll in[maxn];//存最小入边权，pre[v]为该边的起点

ll Directed_MST(int root, int V, int E) {
    ll ret=0;//存最小树形图总权值
    while(1) {
        //1.找每个节点的最小入边
        for(int i=0; i<V; ++i) in[i]=INF;//初始化为无穷大
        for(int i=0; i<E; ++i) {//遍历每条边
            int u=edge[i].u;
            int v=edge[i].v;
            if(edge[i].w<in[v]&&u!=v) {
                pre[v]=u;
                in[v]=edge[i].w;
                if(u==root) pos=i;
            }
        }
        for(int i=0; i<V; ++i) {//判断是否存在最小树形图
            if(i==root) continue;
            if(in[i]==INF) return -1;
        }
        //2.找环
        int cnt=0; //记录环数
        memset(id,-1,sizeof(id));
        memset(vis,-1,sizeof(vis));
        in[root]=0;
        for(int i=0; i<V; ++i) {//标记每个环
            ret+=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<V; ++i) if(id[i]==-1) id[i]=cnt++;
        //3.建立新图 缩点，重新标记
        for(int i=0; i<E; ++i) {
            int u=edge[i].u;
            int v=edge[i].v;
            edge[i].u=id[u];
            edge[i].v=id[v];
            if(id[u]!=id[v]) edge[i].w-=in[v];//减去in[v]的原因是若选择这条边，则不需要选择已经选择过的v的那条最小入边，因此要把那条入边减去
        }
        V=cnt, root=id[root];
    }
    return ret;
}

int main() {
    //ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m)!=EOF) {
        ll sum=0;
        for(int i=0; i<m; ++i) {
            scanf("%d%d%lld", &edge[i].u, &edge[i].v, &edge[i].w);
            sum+=edge[i].w;
        }
        sum++;
        for(int i=m; i<m+n; ++i) {//增加超级节点n，节点n到其余个个节点的边权相同（此题中，边权要大于原图的总边权）
            edge[i].u=n;
            edge[i].v=i-m+1;
            edge[i].w=sum;
        }
        ll ans=Directed_MST(n,n+1,m+n);
        //n+1为总结点数，m+n为总边数
        //ans代表以超级节点0为根的最小树形图的总权值
        //将ans减去sum,如果差值小于sum，说明节点0的出度只有1，即原图是连通图
        //如果差值>=sum，那么说明节点0的出度不止为1，即原图不是连通图
        if(ans==-1||ans-sum>=sum) printf("impossible
");
        else printf("%lld %d
", ans-sum, pos-m);
        puts("");
    }
}