2013-team4/code/edmonds

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
单源点的最小树形图，时间复杂度O(VE)，不能输出方案
其他类型：
1. 题目要求在结点a[1],a[2],..,a[k]中，必须且只能选择一个结点为根
    建立超级根r，并连接至每个a[i]，权值为INF
    然后调用此模板，将返回值减去INF即为答案
    如果减去后的权值之和大于等于INF，则说明无解
    注意，这种情况下权值的类型必须是long long

2. 题目要求在结点a[1],a[2],..,a[k]中，可以选择任意数量个结点为根
    建立超级根r，并连接至每个a[i]，权值为0
    然后调用此模板，所得返回值即为答案
}}}

{{{
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef int etype;
const int MAXM=40000+10;
const int MAXN=1000+10;
const int inf=100000000;

struct node
{
    int u, v;
    etype w;
};

etype in[MAXN]; //和pre[]数组一起,储存每个点的最小入边
int pre[MAXN], idx[MAXN], q[MAXN];
node E[MAXM];

etype edmonds(int root, int n, int m)
{
    etype ret=0;
    int cnt;
    while (1)
    {
        for (int i=0; i<=n; i++) in[i]=inf;
        for (int u, v, i=0; i<m; i++) 
        {
            u=E[i].u, v=E[i].v;
            if (u!=v&&in[v]>E[i].w) pre[v]=u, in[v]=E[i].w;
        }
        pre[root]=-1, in[root]=0; cnt=0;
        for (int i=1; i<=n; i++) if (in[i]==inf) return -1;
        for (int i=1; i<=n; i++) idx[i]=-1, ret+=in[i];
        for (int i=1; i<=n; i++)
        {
            if (idx[i]>=0) continue;
            int r=0;
            for (int j=i; j>=0&&idx[j]<0;)
            {
                if (idx[j]==-2) 
                {
                    idx[j]=++cnt;
                    while (q[--r]!=j) idx[q[r]]=cnt;
                }
                else idx[q[r++]=j]=-2, j=pre[j];
            }
            while (r--) idx[q[r]]=++cnt;
        }
        if (cnt==n) break;
        for (int j, i=0; i<m; i++)
        {
            j=E[i].v, E[i].u=idx[E[i].u], E[i].v=idx[E[i].v];
            if (E[i].u!=E[i].v) E[i].w-=in[j];
        }
        n=cnt; root=idx[root];
    }
    return ret;
}

int main()
{
    int T; scanf("%d", &T);
    for (int cas=1; cas<=T; cas++)
    {
        int n, m, e=0;
        scanf("%d%d", &n, &m); n--;
        while (m--) scanf("%d%d%d", &E[e].u, &E[e].v, &E[e].w), e+=(E[e].u!=E[e].v);
        int ret=edmonds(0, n, e);
        if (ret<0) printf("Case #%d: Possums!\n", cas);
        else printf("Case #%d: %d\n", cas, ret);
    }
    return 0;
}
}}}

单源点的最小树形图，时间复杂度O(VE)，不能输出方案
其他类型：
1. 题目要求在结点a[1],a[2],..,a[k]中，必须且只能选择一个结点为根
    建立超级根r，并连接至每个a[i]，权值为INF
    然后调用此模板，将返回值减去INF即为答案
    如果减去后的权值之和大于等于INF，则说明无解
    注意，这种情况下权值的类型必须是long long
2. 题目要求在结点a[1],a[2],..,a[k]中，可以选择任意数量个结点为根
    建立超级根r，并连接至每个a[i]，权值为0
    然后调用此模板，所得返回值即为答案

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef int etype;
const int MAXM=40000+10;
const int MAXN=1000+10;
const int inf=100000000;
struct node
{
    int u, v;
    etype w;
};
etype in[MAXN]; //和pre[]数组一起,储存每个点的最小入边
int pre[MAXN], idx[MAXN], q[MAXN];
node E[MAXM];
etype edmonds(int root, int n, int m)
{
    etype ret=0;
    int cnt;
    while (1)
    {
        for (int i=0; i<=n; i++) in[i]=inf;
        for (int u, v, i=0; i<m; i++) 
        {
            u=E[i].u, v=E[i].v;
            if (u!=v&&in[v]>E[i].w) pre[v]=u, in[v]=E[i].w;
        }
        pre[root]=-1, in[root]=0; cnt=0;
        for (int i=1; i<=n; i++) if (in[i]==inf) return -1;
        for (int i=1; i<=n; i++) idx[i]=-1, ret+=in[i];
        for (int i=1; i<=n; i++)
        {
            if (idx[i]>=0) continue;
            int r=0;
            for (int j=i; j>=0&&idx[j]<0;)
            {
                if (idx[j]==-2) 
                {
                    idx[j]=++cnt;
                    while (q[--r]!=j) idx[q[r]]=cnt;
                }
                else idx[q[r++]=j]=-2, j=pre[j];
            }
            while (r--) idx[q[r]]=++cnt;
        }
        if (cnt==n) break;
        for (int j, i=0; i<m; i++)
        {
            j=E[i].v, E[i].u=idx[E[i].u], E[i].v=idx[E[i].v];
            if (E[i].u!=E[i].v) E[i].w-=in[j];
        }
        n=cnt; root=idx[root];
    }
    return ret;
}
int main()
{
    int T; scanf("%d", &T);
    for (int cas=1; cas<=T; cas++)
    {
        int n, m, e=0;
        scanf("%d%d", &n, &m); n--;
        while (m--) scanf("%d%d%d", &E[e].u, &E[e].v, &E[e].w), e+=(E[e].u!=E[e].v);
        int ret=edmonds(0, n, e);
        if (ret<0) printf("Case #%d: Possums!\n", cas);
        else printf("Case #%d: %d\n", cas, ret);
    }
    return 0;
}