UVA1537 Picnic Planning

题解 图论-最小生成树 省选/NOI-
题目链接 编辑文章

题意

求 $N$ 点无向图的最小生成树,满足 $1$ 号节点度数 $\le s$ 。$N\le 30$ 。

题解

思想

考虑构造一个以 $1$ 号节点为根的树,则 $1$ 号节点必须与子树中所有连通块相连。记录去掉 $1$ 号节点后的连通块个数,即 $1$ 号节点的最小度数,为 $tcnt$ 。(题目保证有解即 $tcnt\le s$)

对每个连通块分别求出最小生成树,这样就得到了除 $1$ 号节点外的局部最优解,同时全局最优解只与 $1$ 号结点的连法有关

先考虑度数为 $tcnt$ 的最优解,显然从每个连通块选择离 $1$ 最近的节点与之相连最优。

继续考虑度数为 $[tcnt+1,s]$ 时的最优解,可以用换边来解决。

用不在树上的边 $(1,x)$ 替换 $(u,v)$ ,其中 $(u,v)$ 是原树中 $1\rightarrow x$ 路径上的一条边,贪心找权值最大的 $(u,v)$ 替换掉是最优的。

枚举所有 $(1,x)$ 并得到 $(u,v)$ ,设两边的权值为 $z$ 和 $w$ ,显然找到 $w-z$ 最大的 $x_0$ 最优,这样答案就减少了 $w_0-z_0$ 。

这样的换边最多可以做 $s-(tcnt+1)+1=s-tcnt$ 次,不过当 $w_0-z_0\le 0$ 时就可以不用再做了。

实现

  1. map 建立人名和编号的映射,并建边。
  2. dfs1() 划分连通块,并用 v 记录连通块内的所有边,每次搜索完后用 kruskal() 求最小生成树。
  3. v 记录与 $1$ 号节点相连的所有边,同样做一次 kruskal() 。(即从每个连通块选择离 $1$ 最近的节点与之相连,因为连通块都已经用并查集合并了起来,所以这样做是等价的)
  4. 进行 $s-tcnt$ 次换边操作,枚举 $(1,x)$ 并得到边权最大的 $(u,v)$ 记录为 e 。在外层用 mx 保存 $w-z$ 的最大值,同时更新 e0 表示最大时的 $(u,v)$ ,x0 为最大时的 $(1,x)$ 。最后用 x0 替换 e0 即可。如果 $mx\le 0$ 就退出循环。

代码

#include<bits/stdc++.h>

using namespace std;

struct Edge {
    int next,from,to,w;
} edge[1805];
string a,b;
vector <int> v;
map <string,int> mp;
int t,n,m,s,c,cnt,head[35],fa[35];
bool vis[35],used[905],intree[905];

inline bool cmp(int x,int y); //对边进行排序
inline void add(int u,int v,int w); //加边
inline void init(); //多组数据初始化
inline int another(int x); //前向星中相反的边(从1开始)

// 并查集相关
inline void init2(); //初始化
int getfa(int x); //得到父亲
inline bool merge(int x,int y); //合并

void dfs1(int x); //求连通块
bool dfs2(int x,int f,int goal,int &now,int &e0); //求树上1->x
inline int kruskal(); //最小生成树

signed main()
{
    cin>>t;
    while (t--)
    {
        init();
        mp["Park"]=1;
        cin>>m;
        for (int i=1;i<=m;i++)
        {
            cin>>a>>b>>c;
            if (!mp.count(a)) mp[a]=++n;
            if (!mp.count(b)) mp[b]=++n;
            add(mp[a],mp[b],c);
            add(mp[b],mp[a],c); //建边
        }
        cin>>s;
        init2();
        vis[1]=1;
        int ans=0,tcnt=0;
        for (int i=head[1];i;i=edge[i].next) //步骤1
        {
            int y=edge[i].to;
            if (vis[y]) continue;
            tcnt++; //连通块个数
            v.clear();
            dfs1(y);
            ans+=kruskal(); //加上连通块内最小生成树的权值
        }
        v.clear();
        for (int i=head[1];i;i=edge[i].next) v.emplace_back(i); //步骤2
        ans+=kruskal();
        int tot=s-tcnt;
        while (tot--)
        {
            int mx=0,x0,e0; //e0=(u0,v0),x0=(1,x0)
            for (int i=head[1];i;i=edge[i].next)
            {
                if (intree[i] || intree[another(i)]) continue;
                int x=edge[i].to,z=edge[i].w,w=0,e;
                dfs2(1,0,x,w,e); //得到最大权值w和那条边e
                if (w-z>mx)
                {
                    mx=w-z;
                    x0=i;
                    e0=e;
                }
            }
            if (mx<=0) break;
            intree[e0]=intree[another(e0)]=0;
            intree[x0]=intree[another(x0)]=1; //换边
            ans-=mx; //更新答案
        }
        cout<<"Total miles driven: "<<ans<<"\n";
        if (t) puts(""); //注意最后一行不换行
    }
    return 0;
}

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].from=u;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void init()
{
    n=1;
    cnt=0;
    mp.clear();
    memset(vis,0,sizeof(vis));
    memset(used,0,sizeof(used));
    memset(head,0,sizeof(head));
    memset(intree,0,sizeof(intree));
}

inline int another(int x) { return ((x-1)^1)+1; }

inline bool cmp(int x,int y) { return edge[x].w<edge[y].w; }

inline void init2() { for (int i=1;i<=n;i++) fa[i]=i; }

int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]); }

inline bool merge(int x,int y)
{
    int gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    fa[gfx]=gfy;
    return 1;
}

void dfs1(int x)
{
    vis[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y!=1 && !used[i]) used[i]=used[another(i)]=1,v.emplace_back(i); //记录边
        if (!vis[y]) dfs1(y);
    }
}

inline int kruskal()
{
    int ans=0;
    sort(v.begin(),v.end(),cmp);
    for (auto i:v)
    {
        int x=edge[i].from,y=edge[i].to,w=edge[i].w;
        if (!merge(x,y)) continue;
        ans+=w;
        intree[i]=intree[another(i)]=1;
    }
    return ans;
}

bool dfs2(int x,int f,int goal,int &now,int &e0)
{
    if (x==goal) return 1; //能到达终点
    bool flag=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        if (!intree[i]) continue;
        int y=edge[i].to,w=edge[i].w;
        if (y==f) continue;
        bool res=dfs2(y,x,goal,now,e0);
        if (res && w>now) now=w,e0=i; //能到达终点才更新
        flag|=res;
    }
    return flag;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。