POJ1639

Description

给出一张n(n≤20)个点的无向边权图并钦定点P，求使得点P的度不超过k的最小生成树。

Solution

首先无视掉与P相连的所有边，原图会变成若干互不连通的t个块。对每个块分别求MST，再从每个块向P连一条最小的边，这样就得到了一个t度最小生成树。不存在度数比t小的生成树了，因为这t个部分只能通过P来连通。这个比较容易理解。
然后考虑如何从t度MST转移为t+1度MST。我们可以尝试加入一条与P相连的边，图中会出现一个环，从环上再删掉一条最大的边就可以得到一棵t+1度生成树。枚举所有与P相连且不在当前的生成树上的边，最小化总权值就好啦。每次转移可以通过BFS找出路径(P,v)上的最大边是哪条。

时间复杂度O(mlogm+kn)。

Code

//Picnic Planning
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
map<string,int> p;
int const N=30;
int const INF=0x3F3F3F3F;
int n,m,rt;
//图的存储
int e[N][N],cnt;
struct edge{int u,v,c; edge(int u1=0,int v1=0,int c1=0){u=u1,v=v1,c=c1;};} ed[N*N],mx[N];
void edAdd(int u,int v,int c)
{
    e[u][v]=e[v][u]=min(e[u][v],c);
    if(u!=rt&&v!=rt) ed[++cnt]=edge(u,v,c);
}
//划分块相关
int clCnt,f[N];
void extend(int u)
{
    for(int v=1;v<=n;v++)
        if(e[u][v]<INF&&!f[v]) f[v]=f[u],extend(v);
}
//生成树相关
int sum; bool tr[N][N];
void trSet(int u,int v,bool opt) {tr[u][v]=tr[v][u]=opt; sum+=(opt?1:-1)*e[u][v];}
bool cmpC(edge x,edge y) {return x.c<y.c;}
int fa[N];
int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);}
void Kruskal()
{
    sort(ed+1,ed+cnt+1,cmpC);
    for(int u=1;u<=n;u++) fa[u]=u;
    for(int i=1;i<=cnt;i++)
    {
        int u=ed[i].u,v=ed[i].v;
        if(find(u)==find(v)) continue;
        fa[find(v)]=find(u); trSet(u,v,true);
    }
}
//生成树转移相关
int toRt[N];
int q[N],op,cl;
void bfs()
{
    op=cl=0; memset(mx,0,sizeof mx);
    q[++cl]=rt; mx[rt].c=-1;
    while(op<cl)
    {
        int u=q[++op];
        for(int v=1;v<=n;v++)
        {
            if(!tr[u][v]||mx[v].c) continue;
            q[++cl]=v; mx[v]=e[u][v]>mx[u].c?edge(u,v,e[u][v]):mx[u];
        }
    }
}
int main()
{
    scanf("%d",&m);
    n=0; rt=0; memset(e,0x3F,sizeof e);
    for(int i=1;i<=m;i++)
    {
        string s1,s2; int c;
        cin>>s1; cin>>s2; scanf("%d",&c);
        if(!p[s1]) p[s1]=++n; if(!p[s2]) p[s2]=++n;
        if(s1=="Park") rt=p[s1]; if(s2=="Park") rt=p[s2];
        edAdd(p[s1],p[s2],c);
    }
    int k; scanf("%d",&k);
    //划分块
    f[rt]=n+1; clCnt=0;
    for(int i=1;i<=n;i++) if(f[i]==0) f[i]=++clCnt,extend(i);
    //建立clCnt度MST
    sum=0; Kruskal();
    for(int v=1;v<=n;v++) if(e[rt][v]<e[rt][toRt[f[v]]]) toRt[f[v]]=v;
    for(int i=1;i<=clCnt;i++) trSet(rt,toRt[i],true);
    //由t-1度MST转化为t度MST
    for(int t=clCnt+1;t<=k;t++)
    {
        int v0=0,dlt=INF; bfs();
        for(int v=1;v<=n;v++)
            if(!tr[rt][v]&&e[rt][v]<INF)
                if(e[rt][v]-mx[v].c<dlt) dlt=e[rt][v]-mx[v].c,v0=v;
        if(dlt>=0) break;
        trSet(mx[v0].u,mx[v0].v,false);
        trSet(rt,v0,true);
    }
    printf("Total miles driven: %d",sum);
    return 0;
}

P.S.

又是坑爹的读入…还要注意细节