hdu 2121无根最小树形图要建一个虚拟节点

#include<stdio.h>

#include<string.h>

#define inf 999999999

#define N  1100

struct node {

int u,v,w;

}edge[11000];

int visit[N],dis[N],id[N],pre[N],yong,n,index;

void addedge(int u,int v,int w){

edge[yong].u=u;

edge[yong].v=v;

edge[yong++].w=w;

}

int  zhuliu(int root) {//朱刘算法模板

 int sum=0;

 n++;

 while(1) {

        int i;

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

        dis[i]=inf;

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

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

        for(i=0;i<yong;i++) {

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

            if(dis[v]>edge[i].w&&u!=v){

                pre[v]=u;

                dis[v]=edge[i].w;

                if(u==root)//记录最后与根节点连接的边

                    index=i;

            }

        }

        pre[root]=root;

        dis[root]=0;

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

                if(i==root)continue;

            if(dis[i]==inf)return -1;

            sum+=dis[i];

        }

        int res=0;

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

            if(visit[i]==-1) {

            int v=i;

            while(visit[v]==-1) {

                visit[v]=i;

              v=pre[v];

            }

            if(visit[v]!=i||v==root)

                continue;

            int u;

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

                id[u]=res;

            id[v]=res++;

        }

        if(res==0)

            return sum;

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

            if(id[i]==-1)

                id[i]=res++;

        }

        for(i=0;i<yong;i++) {

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

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

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

        }

        n=res;root=id[root];

 }

 return sum;

}

int main(){

   int m,i,j,k,maxx,mm;

   while(scanf("%d%d",&n,&m)!=EOF) {

        yong=0;

        maxx=0;

        mm=m;//记录m

    while(m--) {

        scanf("%d%d%d",&i,&j,&k);

        maxx+=k;//记录最大值

        addedge(i,j,k);

    }

    maxx++;//增1

   for(i=0;i<n;i++)//会记录第几次加入的边

 addedge(n,i,maxx);//建立一个虚拟节点

 k=zhuliu(n);

    if(k==-1||k-maxx>=maxx)

        printf("impossible\n");

    else

    printf("%d %d\n",k-maxx,index-mm);//实际上的根节点是减去m

    printf("\n");

   }

return 0;

}
巴特西

hdu 2121无根最小树形图要建一个虚拟节点

最新文章

热门文章
