hdu2121 最小树形图的虚根

时间：2022-10-23 00:20:46

/*

最小树形图的第二题，终于有了一些理解

具体看注释

*/

/*

无定根的最小树形图

建立虚root

每次只找最短的那条入边

最小树形图理解：

    第一步：寻找最短弧集E：扫一遍所有的边，找到每个点权值最小的入边，这一步会产生环

    第二步：对每个点 i 找环：通过第一步记录的前驱找环，如果找到了原点或退到了另一个环，点i找环失败

    第三步：缩点，缩点就是染色，把每个环内的点染上同一种颜色，每个环内点打上同一个id

    第四步：更新一次边集：如果一条边连接两个不同颜色的点，就该边这条边的权值

重复以上四步。

最小树形图的root：root不需要入边

最小树形图的实质是最小生成树，所以用贪心的思想解决，但是贪心找入边时会生产环（第一步）

                            因此还得找另外一条边连到那个环中，才能解决这个环（第四步）

不定根确定根需要加一个虚根，由虚根为超级源点建立最小生成树，

这样由超级源点出发到达的第一个点就是实际最小生成树的根

虚根和每条边链接一条虚边，其权值要大于实根的和，以此判断是否连了两条虚边（建图失败）

如何找到那个实根：在不断形成环的过程中，会最先有一个点最先和虚根相连，这个点就是实根（实根是不需要入边的，但是在加了虚根后，实根不再是根）

    贪心思想保证第一个和虚根链接的必定是实根

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#define ll long long

#define MAXN 1005

#define INF 0x3f3f3f

using namespace std;

struct Edge{

    ll u,v,cost;

}edge[MAXN*MAXN];

ll pos;

int pre[MAXN],id[MAXN],visit[MAXN];

ll in[MAXN];

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

    int res=;

    int u,v;

    while(){

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

            in[i]=INF;

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

            if(edge[i].u!=edge[i].v && edge[i].cost<in[edge[i].v]){

                in[edge[i].v]=edge[i].cost;

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

                if(edge[i].u==root)

                    pos=i;

            }

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

            if(i!=root && in[i]==INF)

                return -;

        int tn=;

        memset(id,-,sizeof id);

        memset(visit,-,sizeof visit);

        in[root]=;

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

            res+=in[i];

            v=i;

            while(visit[v]!=i && id[v]==- && v!=root){

                visit[v]=i;

                v=pre[v];

            }

            if(v!=root && id[v]==-){

                for(int u=pre[v];u!=v;u=pre[u])

                    id[u]=tn;

                id[v]=tn++;

            }

        }

        if(tn==)

            break;//已经没有环了

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

            if(id[i]==-)

                id[i]=tn++;

        for(int i=;i<m;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].cost-=in[v];

        }

        n=tn;

        root=id[root];

    }

    return res;

}

int main(){

    ll n,m;

    while(scanf("%lld%lld",&n,&m)==){

        ll sum=;

        for(ll i=;i<m;i++){

            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost);

            edge[i].u++;edge[i].v++;

            sum+=edge[i].cost;

        }

        int root=n,tot=m;//加入虚根

        for(ll i=m;i<n+m;i++){

            edge[i].u=;

            edge[i].v=i-m+;

            edge[i].cost=sum+;

        }

        ll ans=zhuliu(,n+,n+m);

        if(ans==- || ans-(sum+)>=sum+)

            printf("impossible\n\n");

        else

            printf("%lld %lld\n\n",ans-(sum+),pos-m);

    }

    return ;

}

相关文章