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

心已赠人 2022-06-06 03:58 123阅读 0赞

# Ice\_cream’s world II #

After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice\_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice\_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.

## Input ##

Every case have two integers N and M (N<=1000, M<=10000), the cities numbered 0…N-1, following M lines, each line contain three integers S, T and C, meaning from S to T have a road will cost C.

## Output ##

If no location satisfy the queen’s require, you must be output “impossible”, otherwise, print the minimum cost in this project and suitable city’s number. May be exist many suitable cities, choose the minimum number city. After every case print one blank.

## Sample Input ##

3 1
    0 1 1
    
    4 4
    0 1 10
    0 2 10
    1 3 20
    2 3 30

## Sample Output ##

impossible
    
    40 0

题意：queen想找一个最好的位置，能够到其它所有点并且路径最短。因为不知道位置，所以是无根的最小树形图。无根的最小树形图区别于最小树形图的地方在于要建立一个超级源点，并且使源点到其它所有点都有一条单向路径，且权值为所有路径权值的和sum=sum+1；最后求的值是路径的总权值+超级源点到实根的权值，如果求得的值ans>=2\*sum，则代表多了一个实根，或者返回了-1，则都代表最小树形图不成立。至于实根，因为超级源点到其它点的值的建立是在所有路径之后，先加入的是未加虚根的最小入权值，只有真正的根最小入权值没变，因为没有其它入边，其它的根的最小入权值已经一定比sum+1要小了，实根的值还为INF。就可以把实根的下标保存，最后下标值减去前M条边，就是实根。

#include<iostream>///HDU - 2121 Ice_cream’s world II  无根最小生成树 朱刘算法＋虚根
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #define INF 0x3f3f3f3f
    const int MAXN=1005;
    using namespace std;
    struct Edge
    {
        int u;///起始点
        int v;///终节点
        int w;///权值
    }edge[MAXN*MAXN];
    int closest[MAXN];///距离i最近的节点
    int vis[MAXN];///标记
    int id[MAXN];///节点i的新编号
    int in[MAXN];///i的最小入边权值
    int N,M;
    int minroot;
    int zhuliu(int root,int n,int m)///根节点编号，节点数量（0~n-1||0~N），边数量（0~m-1||0~M+N-1）
    {
        int ans=0;
        int i,v,u,cnt;
        while(true)
        {
            for(i=0;i<=n;i++)///初始化所有节点的最小的入边权值都是无穷大
                in[i]=INF;
            for(i=0;i<m;i++)///遍历m条边
            {
                u=edge[i].u;
                v=edge[i].v;
        ///边u->v的权值如果比当前v的最小的入边权值还小，则更新最小权值，更新距离节点v最近的节点是u
                if(u!=v&&edge[i].w<in[v])
                {
                    in[v]=edge[i].w;
                    closest[v]=u;
                    if(u==root)minroot=i;///先加入的是未加虚根的最小入权值，只有真正的根最小入权值没变，其它的根的最小入权值已经一定比sum+1要小了
                }
            }///找每个节点入边的最小权值
            ///除了树根以外，存在一个边没有入边，则不能挑出一些边使nodenum个节点连在一起不存在最小树形图
            for(i=0;i<n;i++)
            {
                if(i==root)continue;
                if(in[i]==INF)return -1;
            }
            ///2.是否存在环
            cnt=0;
            memset(vis,-1,sizeof(vis));
            memset(id,-1,sizeof(id));
            in[root]=0;
            for(i=0;i<n;i++)
            {
                ans+=in[i];///第一轮的时候，会把每个节点的最小入边都加到里面。后面可能会删除边的。
    
                v=i;
                ///从v一直往前找，如果有环则必回到自身，如果无环应该找到根
                while(v!=root&&vis[v]!=i&&id[v]==-1)
                {
                    vis[v]=i;
                    v=closest[v];
                }
                if(v!=root&&id[v]==-1)
                {
                    ///将在一个环中的点缩成一个点，在一个环中的点的cnt(编号)都是相同的
                    for(int u=closest[v];u!=v;u=closest[u])
                    {
                        id[u]=cnt;
                    }
                    id[v]=cnt++;
                }
            }
            if(cnt==0)///cnt为0，代表无环，如果有环必进if条件，进if条件cnt比仍然加加
                break;
            for(i=0;i<n;i++)
            {
                if(id[i]==-1)
                    id[i]=cnt++;
            }
            ///构建新的图
            for(i=0;i<m;i++)
            {
                int u=edge[i].u;///先保存原来节点的编号
                int v=edge[i].v;
                edge[i].u=id[u];///新图中u,v的编号
                edge[i].v=id[v];
                if(id[u]!=id[v])///u和v不在一个环中
                    edge[i].w=edge[i].w-in[v];
            }
            n=cnt;
            root=id[root];
        }
        return ans;
    }
    int main()
    {
        int S,T,C,sum,q;
        while(scanf("%d%d",&N,&M)!=EOF)
        {
            sum=0;
            for(int i=0;i<M;i++)
            {
                scanf("%d %d %d",&S,&T,&C);
                edge[i].u=S;
                edge[i].v=T;
                edge[i].w=C;
                sum=sum+C;
            }
            sum++;
            for(int i=0;i<N;i++)
            {
                edge[M+i].u=N;///虚根
                edge[M+i].v=i;
                edge[M+i].w=sum;
            }
            int ans=zhuliu(N,N+1,M+N);
            if(ans==-1||ans>=2*sum)
                printf("impossible\n\n");
            else
                printf("%d %d\n\n",ans-sum,minroot-M);
        }
        return 0;
    }