over 3 years ago

看了好久好久的黑书,死活没看懂,最后找了个ppt终于是懂了T_T

度限制最小生成树;(步骤)

假设以v0的限制是k

1、除去v0点,在剩下的点中跑最小生成树,可能会出现多个联通块,联通块个数tot就是满足生成树的最小k

2、从v0点依旧以kruskal的方法将联通块与v0联通

3、从各个联通块中搜一遍,维护best[i],为从v0到i点除去与v0连的边外,cost最大的边

4、从tot+1循环至k

    ①枚举从v0出发的未选择的边j,找出(+j,-cost[best[v[j]]])最小的边。若min>=0 则再更新无用,退出

②把min加入答案,删除best[v[j]]及其反向边,从v[j]出发遍历此连通块,处理best

PAY ATTENTION:

在删边这里纠结了好久,我的做法是像处理链表那样,在next数组里多记录fa,然后用删节点的方式删掉它【MARK:不知道还有什么好方法】

真是太激动了……用了map还开了好多大数组,竟然速度不慢,也没有爆内存。好开心~【当然后来又搞了搞内存和码长~

有几处是需要注意的,程序中作了注释

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<string>
#include<iostream>
#define maxn 3001
#define maxm 500001
#define inf 1000000000
using namespace std;
struct wide{int u,v,w;} a[maxm],b[maxm];
int fa[maxn*2],f[maxn],next[maxn*2],point[maxn],u[maxn*2],v[maxn*2],w[maxn*2],best[maxn];
//注意这里并查集的fa和next链表里的fa不要弄混 maxn*2的原因是最小生成树的边只有n-1条
int n=0,m,widen=-1,bn=0;long long result=0;
//这里widen为-1保证可以通过异或找到反向边
bool can[maxn]={0};
map<string,int> q;
int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
bool cmp(const wide a,const wide b){return a.w<b.w;}
void addedge(int x,int y,int value)
{
    widen++;
    next[widen]=point[x];fa[point[x]]=widen;point[x]=widen;u[widen]=x;v[widen]=y;w[widen]=value;
    widen++;
    next[widen]=point[y];fa[point[y]]=widen;point[y]=widen;u[widen]=y;v[widen]=x;w[widen]=value;
}
int find(int x){if (f[x]==x) return x;return f[x]=find(f[x]);}
void search(int father,int now)
{
    for (int k=point[now];k!=-1;k=next[k])
        if (v[k]!=father)
        {
            if (best[now]==-1) best[v[k]]=k;
            else
              if (w[best[now]]>w[k]) best[v[k]]=best[now];
              else best[v[k]]=k;
            search(now,v[k]);
        }
}
void deletewide(int k)//注意
{
    if (fa[k]==-1)
        {point[u[k]]=next[k];if (next[k]!=-1) fa[next[k]]=-1;}
    else
    {next[fa[k]]=next[k];if (next[k]!=-1)fa[next[k]]=fa[k];}
}
string st1,st2;
int main()
{
    int i,j,k,x,y,tot,temp,minn;
    st1="Park";q[st1]=0;
    m=readln();
    memset(point,-1,sizeof(point));
    memset(next,-1,sizeof(next));
    memset(fa,-1,sizeof(fa));
    for (i=1;i<=m;i++)
    {
        cin>>st1>>st2;
        if (q.find(st1)==q.end()) q[st1]=++n;
        if (q.find(st2)==q.end()) q[st2]=++n;
        a[i].u=q[st1];a[i].v=q[st2];
        a[i].w=readln();
        if (a[i].u==0) {b[++bn].v=a[i].v;b[bn].w=a[i].w;}
        if (a[i].v==0) {b[++bn].v=a[i].u;b[bn].w=a[i].w;}
    }
    k=readln();
    sort(a+1,a+m+1,cmp);
    for (i=1;i<=n;i++) f[i]=i;
    for (i=1;i<=m;i++)
    {
        x=a[i].u;y=a[i].v;
        if (x!=0&&y!=0)
        {
            x=find(x);y=find(y);
            if (x!=y)
            {result+=a[i].w;f[x]=y;
             addedge(a[i].u,a[i].v,a[i].w);}
        }
    }
    tot=0;
    for (i=1;i<=n;i++) tot=tot+(f[i]==i);
    for (i=1;i<=m;i++)
        if (a[i].u==0||a[i].v==0)
        {
            x=find(a[i].u);y=find(a[i].v);
            if (y==0) {int o=x;x=y;y=o;}
            if (x!=y) {result+=a[i].w;f[y]=x;addedge(a[i].u,a[i].v,a[i].w);}
        }
    for (i=point[0];i!=-1;i=next[i]){best[v[i]]=-1;can[v[i]]=true;search(0,v[i]);}
    for (i=tot+1;i<=k&&i<=bn;i++)
    {
        temp=0;minn=inf;
        for (j=1;j<=bn;j++)
            if (can[b[j].v]==false)
                if (minn>b[j].w-w[best[b[j].v]])
                    minn=b[j].w-w[best[b[j].v]],temp=j;
        if (minn>=0) break;
        result+=minn;
        can[b[temp].v]=true;//这里使用的是上面找到的temp边呀
     deletewide(best[b[temp].v]);deletewide(best[b[temp].v]^1);
        best[b[temp].v]=-1;search(0,b[temp].v);
    }
    printf("Total miles driven: %lld\n",result);
}
← 【bzoj1491】【noi2007】社交网络 【poj2728】【最优比例生成树】DESERT KING →
 
comments powered by Disqus