codeforce 240E 最小树形图+路径记录更新

最小树形图的路径是在不断建立新图的过程中更新的，因此需要开一个结构体cancle记录那些被更新的边，保存可能会被取消的边和边在旧图中的id

在朱刘算法最后添加了一个从后往前遍历新建边的循环，这可以理解为回溯，通过cancle结构体不断找到上一个时间点更新的边id，并且取消那些被代替的边

至于为什么要按建图时间从后往前回溯，我在下面举了一个例子：

上图取自朱刘算法标准示例，最小树形图路径保存与更新

拿节点v3举例

指向v3的边有三条：a4，a13，a9

第一次循环：步骤1，2建立最短弧集：a4被保存在最短弧集E中,usedE[4]=1

　　　　　　步骤3：准备新建图，此时a9，a13权值被更新，其旧id被保存在cancle.id中，a4的id被保存在cancle.pre中，假设a9,a13被赋予新id a16，a17

第二次循环：步骤1, 2建立新图：a17被保存在新图中,usedE[17]=1

　　　　　　步骤3：准备建立新图，a16被更新，假设其被赋予新id a18

第三次循环：没有环了，退出循环

退出循环后从后往前便利新建边,依旧拿v3举例

首先是循环到usedE[17]：cancle[17].id=13,因此usedE[13]=1

　　　　　　　　　　　 cancle[17].pre=4,因此usedE[4]=0

最后在遍历被使用边时，可以发现被使用的是边a13，而a4被a13代替了

大家也可以拿其余点自己试试，下面贴上我的代码，codeforce240E，输入输出有点坑，需要从通过文件io

#include<iostream>

#include<cstring>

#include<cstdio>

#define MAXN 100005

#define MAXM MAXN*20

#define INF 0x3f3f3f3f

using namespace std;

struct Edge{

    int u,v,cost;

    int w;//原始权值

    int id;

}edge[MAXM];

inline void addedge(int u,int v,int cost,int w,int id){

    edge[id].cost=edge[id].w=cost;

    edge[id].u=u;

    edge[id].v=v;

    edge[id].id=id;

}

struct Cancle{//

    int pre;//保存可能被取消的那条边的id

    int id;//保存可能新增的那条边更新前的id

}cancle[MAXM];

int pre[MAXN],id[MAXN],vis[MAXN],in[MAXN];

int preid[MAXN],usedE[MAXN];

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

    int res=,total=m;//total是下一条新建边的id

    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]){

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

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

                //更新被加入到边集E的那条边的id

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

            }

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

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

        int tn=;

        memset(id,-,sizeof id);

        memset(vis,-,sizeof vis);

        in[root]=;

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

            res+=in[i];

            int v=i;

            ///将新图中被使用到的边保存

            if(i!=root) usedE[preid[i]]++;

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

                vis[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 v=edge[i].v;

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

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

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

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

                //把这条边的更新信息保存一下

                cancle[total].id=edge[i].id;//注意，这里是保留该边更新前的id！

                cancle[total].pre=preid[v];//原本指向v的边被取消了

                edge[i].id=total++;

            }

        }

        n=tn;

        root=id[root];

    }

    /*

    为什么要从后往前?

    */

    for(int i=total-;i>=m;i--)

        if(usedE[i]){

            usedE[cancle[i].pre]--;

            usedE[cancle[i].id]++;

        }

    return res;

}

int main(){

    freopen("input.txt","r",stdin);

    freopen("output.txt","w",stdout);

    int n,m;

    scanf("%d%d",&n,&m);

    int u,v,w;

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

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

        u--,v--;

        addedge(u,v,w,w,i);

    }

    int root=;

    int res=zhuliu(root,n,m);

    if(res==||res==-)

        printf("%d\n",res);

    else{

        printf("%d\n",res);

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

            if(usedE[i]&&edge[i].w) printf("%d ",i+);

    }

    printf("\n");

    return ;

}

这段代码挂在了test31.。不知道为什么，望大佬指正，非常感谢！

巴特西

codeforce 240E 最小树形图+路径记录更新

最新文章

热门文章