[POJ 3164] | Eurce's Blog

有向图最小生成树

需要用到朱刘-Edmonds算法。算法的基本步骤很简单（证明就略过了）：
（1）从源点出发DFS，若无法到达所有点，最小生成树不存在，直接返回；
（2）找每个结点的最小权入边；
（3）若存在环，将同一环上所有结点进行缩点，对于指向该环内某点的边，将其权值减去该点的最小入边权，重复（2）；若无环，则树已建成。

但实现这个算法却想了整整一天。

分析算法步骤可以发现，（2）中每次选中的各个最小权，其值都属于最小生成树的一部分，一旦某边被选中后，其权值将确定不再修改。因此可以考虑对边作一个标记，表示是否已选走，之后找环时可以直接忽略这些边。另外，缩点操作可能使某些边变成自环，这些边也是要忽略的。

（3）找环时，可以考虑标记各个点，每次从无标记的某个点出发沿入边回溯，若遇到标记相同的点表示找到了环，此时可继续回溯将环上所有点标记为第t步找出的环。然后就是缩点，这里我用到了并查集。首先，需要修改各入边权值。然后，记录各个环上的点原本的父结点，再依次将环上各点与其父结点作并集。最后，将生成的新点入边权值更新为无穷大。这里需要记录原父结点是因为并查集缩点后原来的结点编号就失效了，因此环信息也就被破坏了（在这一步DEBUG了很久才发现问题……）。

最后就是遍历整个边表，将各个有标记的边权值相加，即为最小生成树权值。

时间复杂度方面，迭代部分的找最小权入边O(E)，找环O(V)，更新边权值O(E)，缩点O(V)。以上这些操作最多迭代O(V)次，因此总体时间复杂度是O(VE)的。实在是很漂亮的算法……

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,el,hd[100],b[100],c[100],pl[100],f[100];
int et[100][100];
double x[100],y[100],ans;

struct E
{
    int u,v,b,p;
    double d;
}e[10000];

void adde(int u,int v)
{
    if(!v||u==v||et[u][v])
        return;
    et[u][v]=1;
    e[el].u=u; e[el].v=v; e[el].b=0; e[el].p=hd[u];
    e[el].d=sqrt(pow(x[u]-x[v],2)+pow(y[u]-y[v],2));
    hd[u]=el++;
}

void init()
{
    int i,j,k,l;
    ans=0;
    el=0;
    memset(hd,-1,sizeof hd);
    memset(f,-1,sizeof f);
    memset(et,0,sizeof et);
    for(i=0;i<n;i++)
        if(scanf("%lf%lf",x+i,y+i)==-1)
            return;
    for(i=0;i<m;i++)
    {
        if(scanf("%d%d",&j,&k)==-1)
            return;
        adde(j-1,k-1);
    }
}

int fi(int i)
{
    if(f[i]<0)
        return i;
    else
        return f[i]=fi(f[i]);
}

bool un(int a,int b)
{
    int fa=fi(a),fb=fi(b);
    if(fa==fb)
        return 0;
    if(f[fa]<f[fb])
    {
        f[fa]+=f[fb];
        f[fb]=fa;
    }
    else
    {
        f[fb]+=f[fa];
        f[fa]=fb;
    }
    return 1;
}

void dfs(int i)
{
    int j,k,l;
    b[i]=1;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(!b[j])
            dfs(j);
    }
}

void solve()
{
    int i,j,k,l,ct,t;
    memset(b,0,sizeof b);
    dfs(0);
    for(i=0;i<n&&b[i];i++);
    if(i<n)
    {
        puts("poor snoopy");
        return;
    }
    ct=1;
    memset(c,0,sizeof c);
    memset(pl,-1,sizeof pl);
    while(1)
    {
        for(l=0;l<el;l++)
        {
            if(e[l].b||fi(e[l].u)==fi(e[l].v))
                continue;
            j=fi(e[l].v);
            if(pl[j]==-1||e[l].d<e[pl[j]].d)
                pl[j]=l;
        }
        memset(b,0,sizeof b);
        for(i=1,t=0;i<n;i++)
        {
            j=fi(i);
            e[pl[j]].b=1;
            if(b[j])
                continue;
            b[j]=i;
            for(l=pl[j];l!=-1;l=pl[j])
            {
                j=fi(e[l].u);
                if(b[j]==i)
                {
                    t=1;
                    for(l=pl[j];1;l=pl[k])
                    {
                        k=fi(e[l].u);
                        c[k]=ct;
                        if(k==j)
                            break;
                    }
                    break;
                }
                else if(b[j])
                    break;
                else
                    b[j]=i;
            }
        }
        if(!t)
            break;
        for(l=0;l<el;l++)
        {
            if(e[l].b||fi(e[l].u)==fi(e[l].v))
                continue;
            j=fi(e[l].v);
            if(c[j]==ct)
                e[l].d-=e[pl[j]].d;
        }
        for(i=1;i<n;i++)
            b[i]=fi(i);
        for(i=1;i<n;i++)
            if(c[j=b[i]]==ct)
                un(j,e[pl[j]].u);
        for(i=1;i<n;i++)
            if(c[j=fi(i)]==ct)
                pl[j]=-1;
        ct++;
    }
    for(l=0;l<el;l++)
        if(e[l].b)
            ans+=e[l].d;
    printf("%.2f\n",ans);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,el,hd[100],b[100],c[100],pl[100],f[100];

int et[100][100];

double x[100],y[100],ans;

struct E

{

int u,v,b,p;

double d;

}e[10000];

void adde(int u,int v)

{

if(!v||u==v||et[u][v])

return;

et[u][v]=1;

e[el].u=u; e[el].v=v; e[el].b=0; e[el].p=hd[u];

e[el].d=sqrt(pow(x[u]-x[v],2)+pow(y[u]-y[v],2));

hd[u]=el++;

}

void init()

{

int i,j,k,l;

ans=0;

el=0;

memset(hd,-1,sizeof hd);

memset(f,-1,sizeof f);

memset(et,0,sizeof et);

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

if(scanf("%lf%lf",x+i,y+i)==-1)

return;

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

{

if(scanf("%d%d",&j,&k)==-1)

return;

adde(j-1,k-1);

}

int fi(int i)

{

if(f[i]<0)

return i;

else

return f[i]=fi(f[i]);

}

bool un(int a,int b)

{

int fa=fi(a),fb=fi(b);

if(fa==fb)

return 0;

if(f[fa]<f[fb])

{

f[fa]+=f[fb];

f[fb]=fa;

}

else

{

f[fb]+=f[fa];

f[fa]=fb;

}

return 1;

}

void dfs(int i)

{

int j,k,l;

b[i]=1;

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

if(!b[j])

dfs(j);

}

void solve()

{

int i,j,k,l,ct,t;

memset(b,0,sizeof b);

dfs(0);

for(i=0;i<n&&b[i];i++);

if(i<n)

{

puts("poor snoopy");

return;

}

ct=1;

memset(c,0,sizeof c);

memset(pl,-1,sizeof pl);

while(1)

{

for(l=0;l<el;l++)

{

if(e[l].b||fi(e[l].u)==fi(e[l].v))

continue;

j=fi(e[l].v);

if(pl[j]==-1||e[l].d<e[pl[j]].d)

pl[j]=l;

}

memset(b,0,sizeof b);

for(i=1,t=0;i<n;i++)

{

j=fi(i);

e[pl[j]].b=1;

if(b[j])

continue;

b[j]=i;

for(l=pl[j];l!=-1;l=pl[j])

{

j=fi(e[l].u);

if(b[j]==i)

{

t=1;

for(l=pl[j];1;l=pl[k])

{

k=fi(e[l].u);

c[k]=ct;

if(k==j)

break;

}

break;

}

else if(b[j])

break;

else

b[j]=i;

}

if(!t)

break;

for(l=0;l<el;l++)

{

if(e[l].b||fi(e[l].u)==fi(e[l].v))

continue;

j=fi(e[l].v);

if(c[j]==ct)

e[l].d-=e[pl[j]].d;

}

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

b[i]=fi(i);

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

if(c[j=b[i]]==ct)

un(j,e[pl[j]].u);

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

if(c[j=fi(i)]==ct)

pl[j]=-1;

ct++;

}

for(l=0;l<el;l++)

if(e[l].b)

ans+=e[l].d;

printf("%.2f\n",ans);

}

int main()

{

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

{

init();

solve();

}

return 0;

}

ps：做题到现在为止，第一次用到中国人发明的算法。两位作者中，我只搜到了朱永津，只有这篇文章讲得稍微多点，相关资料出奇的少呢……