[POJ 1639] | Eurce's Blog

度限制最小生成树

给出最多包含最多21个结点的无向图，边权值为正数，求这样的一棵最小生成树：与结点1相连的树边不超过m条。

解法是，先从图中剔除结点1，求最小生成森林。然后重复：遍历结点1相连的所有边，找（1）能联通某森林的最小边；（2）若（1）边不存在，则找加边之后作破圈操作能使树权减少最多的边。直到m次加边机会耗尽或者加边也无法减少树权。

一些小技巧：题目数据量很小，所以邻接矩阵也可以，但如果像我这样习惯用邻接表的话，对树边作标记的时候两个方向的边要同时标记。而由于加边时无向边对应的邻接表项是成对插入的，也即编号仅有最末位不同，所以^1就可以得到另一个方向的边了。这种用邻接表时修改边信息的做法很常用，最开始是在做费用流的题目时学到的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
using namespace std;

int n,m,ans;
int b[22],f[22],el,hd[22],ei[484],eil;
map<string,int>M;
string s;

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

struct CP
{
    bool operator () (const int &p,const int &q) const
    {
        return e[p].d<e[q].d;
    }
};

inline void adde(int u,int v,int d)
{
    ei[eil++]=el;
    e[el].u=u; e[el].v=v; e[el].d=d; 
    e[el].b=0; e[el].p=hd[u]; hd[u]=el++;
    e[el].u=v; e[el].v=u; e[el].d=d; 
    e[el].b=0; e[el].p=hd[v]; hd[v]=el++;
}

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

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

void init()
{
    int i,j,k,l=1;
    memset(f,-1,sizeof f);
    memset(hd,-1,sizeof hd);
    el=eil=ans=0;
    M.clear();
    M["Park"]=l++;
    while(m--)
    {
        cin>>s;
        if(M[s]==0)
            M[s]=i=l++;
        else
            i=M[s];
        cin>>s;
        if(M[s]==0)
            M[s]=j=l++;
        else
            j=M[s];
        cin>>k;
        adde(i,j,k);
    }
    sort(ei,ei+eil,CP());
    cin>>m;
}

int dfs(int i,int f,int mx,int mxl,int t)
{
    int j,k,l;
    if(i==1)
    {
        if(t)
        {
            ans-=mx;
            e[mxl].b=0;
            e[mxl^1].b=0;
        }
        return mx;
    }
    b[i]=1;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(!e[l].b)
            continue;
        if(b[j]||j==f)
            continue;
        if(mx<e[l].d)
        {
            if(k=dfs(j,i,e[l].d,l,t))
                return k;
        }
        else
        {
            if(k=dfs(j,i,mx,mxl,t))
                return k;
        }
    }
    b[i]=0;
    return 0;
}

void solve()
{
    int i,j,k,l,mxl;
    for(i=0;i<eil;i++)
    {
        if(e[ei[i]].u==1||e[ei[i]].v==1)
            continue;
        j=e[ei[i]].u;
        k=e[ei[i]].v;
        if(un(j,k))
        {
            e[ei[i]].b=1;
            e[ei[i]^1].b=1;
            ans+=e[ei[i]].d;
        }
    }
    while(m)
    {
        k=-1;
        for(l=hd[1];l!=-1;l=e[l].p)
        {
            memset(b,0,sizeof b);
            if(e[l].b)
                continue;
            e[l].b=e[l^1].b=1;
            ans+=e[l].d;
            j=dfs(e[l].v,1,e[l].d,l,0);
            if(j!=e[l].d)
            {
                if(!j)
                    j=0x7fffffff-e[l].d;
                if(j-e[l].d>k)
                {
                    k=j-e[l].d;
                    mxl=l;
                }
            }
            e[l].b=e[l^1].b=0;
            ans-=e[l].d;
        }
        if(k==-1)
            break;
        memset(b,0,sizeof b);
        e[mxl].b=e[mxl^1].b=1;
        ans+=e[mxl].d;
        dfs(e[mxl].v,1,e[mxl].d,l,1);
        m--;
    }
    printf("Total miles driven: %d\n",ans);
}

int main()
{
    while(cin>>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

172

173

174

175

176

177

178

179

180

181

182

183

184

185

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<map>

using namespace std;

int n,m,ans;

int b[22],f[22],el,hd[22],ei[484],eil;

map<string,int>M;

string s;

struct E

{

int u,v,d,b,p;

}e[484];

struct CP

{

bool operator () (const int &p,const int &q) const

{

return e[p].d<e[q].d;

}

};

inline void adde(int u,int v,int d)

{

ei[eil++]=el;

e[el].u=u; e[el].v=v; e[el].d=d;

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

e[el].u=v; e[el].v=u; e[el].d=d;

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

}

int fi(int i)

{

if(f[i]<0)

return i;

else

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

}

int un(int a,int b)

{

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

if(fa==fb)

return 0;

int na=f[fa],nb=f[fb];

if(na<nb)

{

f[fa]+=nb;

f[fb]=fa;

}

else

{

f[fb]+=na;

f[fa]=fb;

}

return 1;

}

void init()

{

int i,j,k,l=1;

memset(f,-1,sizeof f);

memset(hd,-1,sizeof hd);

el=eil=ans=0;

M.clear();

M["Park"]=l++;

while(m--)

{

cin>>s;

if(M[s]==0)

M[s]=i=l++;

else

i=M[s];

cin>>s;

if(M[s]==0)

M[s]=j=l++;

else

j=M[s];

cin>>k;

adde(i,j,k);

}

sort(ei,ei+eil,CP());

cin>>m;

}

int dfs(int i,int f,int mx,int mxl,int t)

{

int j,k,l;

if(i==1)

{

if(t)

{

ans-=mx;

e[mxl].b=0;

e[mxl^1].b=0;

}

return mx;

}

b[i]=1;

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

{

j=e[l].v;

if(!e[l].b)

continue;

if(b[j]||j==f)

continue;

if(mx<e[l].d)

{

if(k=dfs(j,i,e[l].d,l,t))

return k;

}

else

{

if(k=dfs(j,i,mx,mxl,t))

return k;

}

b[i]=0;

return 0;

}

void solve()

{

int i,j,k,l,mxl;

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

{

if(e[ei[i]].u==1||e[ei[i]].v==1)

continue;

j=e[ei[i]].u;

k=e[ei[i]].v;

if(un(j,k))

{

e[ei[i]].b=1;

e[ei[i]^1].b=1;

ans+=e[ei[i]].d;

}

while(m)

{

k=-1;

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

{

memset(b,0,sizeof b);

if(e[l].b)

continue;

e[l].b=e[l^1].b=1;

ans+=e[l].d;

j=dfs(e[l].v,1,e[l].d,l,0);

if(j!=e[l].d)

{

if(!j)

j=0x7fffffff-e[l].d;

if(j-e[l].d>k)

{

k=j-e[l].d;

mxl=l;

}

e[l].b=e[l^1].b=0;

ans-=e[l].d;

}

if(k==-1)

break;

memset(b,0,sizeof b);

e[mxl].b=e[mxl^1].b=1;

ans+=e[mxl].d;

dfs(e[mxl].v,1,e[mxl].d,l,1);

m--;

}

printf("Total miles driven: %d\n",ans);

}

int main()

{

while(cin>>m)

{

init();

solve();

}

return 0;

}