hdu4966 最小树形图+虚根

时间：2021-09-20 08:55:56

/*

辛辛苦苦调试半天，

过了样例，竟然没有ac！！

网上对比了ac代码，感觉添加一个虚根就能ac

但是想不明白为什么

*/

/*

第二天想了下，知道了为什么wa：因为从等级0连到其他课程等级i的不止一门课，如果不加虚根，仅仅是通过判断L1[i]==0来决定根节点显然是会错的

添加根节点能保证生成的是最小树形图

*/

我的代码

/*

hdu4966

第i门课从0到a[i]个等级，从最开始所有课都是0级，目标所有课到*

M条路，如果第i门课达到L1[i]，那么通过M后，第j门课到达L2[i]

N，M

a[i] .. a[N]

接下来M行c[i], L1[i], d[i], L2[i], money[i]

边权当然是money，每门课拆成a[i]个等级(500个点)

每门课的a[i]到a[i]-1连一条权值为0的边

增加一个超级源点，和每门课level 0连在一起

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define MAXN 505

#define INF 0x3f3f3f

using namespace std;

struct Edge{

    int u,v,cost;

}edge[MAXN*MAXN];

int a[MAXN];//等级

int V[MAXN][MAXN];//点集

int c[MAXN],L1[MAXN],d[MAXN],L2[MAXN],money[MAXN];

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

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

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

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

            }

        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];

            v=i;

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

                vis[v]=i;

                v=pre[v];

            }

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

                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 totm;

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

    edge[totm].u=u;

    edge[totm].v=v;

    edge[totm].cost=w;

    totm++;

}

int main(){

    int n,m,totn;

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

        totn=totm=;

        memset(V,,sizeof V);

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

            scanf("%d",&a[i]);

            for(int j=;j<=a[i];j++){

                V[i][j]=totn++;

                if(j!=)

                    addedge(V[i][j],V[i][j-],);

            }

        }

        int sum=,root=;

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

            scanf("%d%d%d%d%d",&c[i],&L1[i],&d[i],&L2[i],&money[i]);

            if(L1[i]==)

                root=c[i];

            addedge(V[c[i]][L1[i]],V[d[i]][L2[i]],money[i]);

            sum+=money[i];

        }

        if(root==){

            printf("-1\n");

            continue;

        }

        int ans=zhuliu(root,totn,totm);

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

    }

    return ;

}

ac代码

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int maxn = , maxm =  * , inf = 1e9;

struct Edge{

    int u, v, w;

    Edge(){}

    Edge(int u, int v, int w):

    u(u), v(v), w(w){}

}e[maxm];

int ec;

int lev[], begid[], endid[];

int N;

int mincost[maxn], pre[maxn];

bool makeMin(int root){

    for(int i = ; i <= N; i++) mincost[i] = inf;

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

        if(e[i].u == e[i].v) continue;

        int v = e[i].v;

        if(mincost[v] > e[i].w){

            mincost[v] = e[i].w;

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

        }

    }

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

        if(i == root) continue;

        if(mincost[i] == inf) return false;

    }

    return true;

}

int vis[maxn];

int id[maxn];

bool existCircle(int root, int &res){

    memset(vis, -, sizeof(vis));

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

    int ind = ;

    mincost[root] = ;

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

        int v = i;

        res += mincost[i];

        while(vis[v] != i && v != root && 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] = ind;

            id[v] = ind++;

        }

    }

    if(ind == ) return false;

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

        if(id[i] == -) id[i] = ind++;

    N = ind - ;

    return true;

}

void update(){

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

        int v = e[i].v;

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

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

        if(e[i].u == e[i].v) continue;

        e[i].w -= mincost[v];

    }

}

int DMST(int root){

    int res = ;

    while(){

        if(!makeMin(root)) return -;

        if(!existCircle(root, res)) return res;

        update();

        root = id[root];

    }

    return -;

}

int main(){

//    freopen("in", "r", stdin);

//    freopen("out", "w", stdout);

    int n, m;

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

        for(int i = ; i <= n; i++) scanf("%d", lev+i);

        lev[] = , begid[] = ;

        for(int i = ; i <= n; i++) begid[i] = begid[i-] + lev[i-] + ;

        N = begid[n] + lev[n];

        int c, l, d, r, w;

        int root = ;

        ec = ;

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

        e[ec++] = Edge(root, begid[i], );

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

            for(int j = ; j <= lev[i]; j++){

                int u = begid[i] + j, v = u - ;

                e[ec++] = Edge(u, v, );

            }

        }

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

            scanf("%d%d%d%d%d", &c, &l, &d, &r, &w);

            int v = begid[d] + r;

            for(int j = l, u = begid[c] + l; j <= lev[c]; u++, j++){

                e[ec++] = Edge(u, v, w);

            }

        }

        int ans = DMST(root);

        if(~ans) printf("%d\n", ans);

        else puts("-1");

    }

    return ;

}

相关文章