问题描述

给你一张含有n个点m条边的无向图,求出一个最小生成树,满足1号节点的度数不超过给定整数s。

输入

第一行给出一个整数m,表示有m条边。
接下来m行,每一行有两个字符串表示节点以及它们之间的距离。
最后一行给出整数s。

输出

输出一行:Total miles driven: xxx
xxx 表示最小生成树的边权之和。

思路

其实这个东西说的高大上一点是度限制生成树,但是本身并不难理解。

首先是用常规的Kruskal建一个最小生成树,然后把这棵生成树去掉1号节点。统计有多少个联通块,联通块个数记为t,然后从1号点和每一个联通块连一条最短的边。这样一来我们就得出了一个一号节点度数为t的最小生成树。

如果t大于s,则不存在题目要求的树(当然本题不包含这种情况)。
如果t等于s,则不需要其他操作,直接输出边权之和就好了。
如果t小于s,则我们需要调整这棵树,使它的边权之和更小。

调整这棵树,我们可以改动s-t条边(或者更少)。考虑从1号节点出发的每一条边,设它的到达节点x,边权为z。如果该边不在生成树中,则我们可以找出从1号点到x号点树上路径的最长边,设该边边权为y(这个我们可以通过一次dfs预处理出来)。那么我们可以找出一个节点x,使它的z-y最大。z-y就是这次调整能够减少的最大边权(把最长边去掉,加上从1出发到达x的这条边)。重复这次操作s-t次,就可以得到题目要求的最小生成树。

细节

  1. 如果上文中的z-y为负数,则以后不进行任何操作,输出答案即可
  2. 树和图要分开来存,进行调整时不要搞混了
  3. 反正代码很难打QWQ,思路一定要清晰

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <iostream>
#define MAXN 35
#define INF 0x3f3f3f3f
using namespace std;

int n=1, m, t, s, z, tree[MAXN][MAXN], graph[MAXN][MAXN], ans;
int f[MAXN], min_dis[MAXN], min_to[MAXN];
string x, y;
map <string, int> mmp;
pair<int, int> edge[MAXN*MAXN], maxe[MAXN];

bool CMP(pair<int, int> x, pair<int, int> y)
{
    return graph[x.first][x.second]<graph[y.first][y.second];
}

void init()
{
    mmp["Park"]=1;
    memset(graph, 0x3f, sizeof(graph));
    memset(tree, -1, sizeof(tree));
    memset(min_dis, 0x3f, sizeof(min_dis));
    for(int i=1; i<MAXN; i++) f[i]=i;
}

int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

void Kruskal()
{
    for(int i=1; i<=n; i++) f[i]=i;
    sort(edge+1, edge+m+1, CMP);
    for(int i=1; i<=m; i++)
    {
        int x=edge[i].first, y=edge[i].second;
        int fx=find(x), fy=find(y);
        if(fx==fy || x==1 || y==1) continue;
        f[fx]=fy;
        tree[y][x]=tree[x][y]=graph[x][y];
        ans+=graph[x][y];
    }
}

void dfs(int x, int fa)
{
    for(int i=2; i<=n; i++)
    {
        if(i==fa || tree[x][i]==-1) continue;
        int u=maxe[x].first, v=maxe[x].second;
        if(tree[u][v]>tree[x][i]) maxe[i]=make_pair(u, v);
        else maxe[i]=make_pair(x, i);
        dfs(i, x);
    }
}


int main()
{
    ios::sync_with_stdio(false);
    init();
    scanf("%d", &m);
    for(int i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        if(mmp[x]==0) mmp[x]= ++n;
        if(mmp[y]==0) mmp[y]= ++n;
        graph[mmp[x]][mmp[y]]=z;
        graph[mmp[y]][mmp[x]]=z;
        edge[i]=make_pair(mmp[x], mmp[y]);
    }
    scanf("%d", &s);
    Kruskal();
    for(int i=2; i<=n; i++)
    {
        int x=find(i);
        if(min_dis[x]>graph[1][i])
        {
            min_dis[x]=graph[1][i];
            min_to[x]=i;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(min_dis[i]==INF) continue;
        tree[1][min_to[i]]=min_dis[i];
        tree[min_to[i]][1]=min_dis[i];
        ans+=min_dis[i]; t++;
    }
    for(int i=t+1; i<=s; i++)
    {
        int minn=INF, to, u, v;
        memset(maxe, 0, sizeof(maxe));
        dfs(1, -1);
        for(int j=2; j<=n; j++)
        {
            int x=maxe[j].first, y=maxe[j].second;
            if(minn<graph[1][j]-tree[x][y]) continue;
            minn=graph[1][j]-tree[x][y];
            to=j; u=x, v=y;
        }
        if(minn>=0) break;
        tree[1][to]=tree[to][1]=graph[1][to];
        tree[u][v]=tree[v][u]=-1;
        ans+=minn;
    }
    printf("Total miles driven: %d\n", ans);
}

1 对 “POJ1639 Picnic Planning [最小生成树]”的想法;

  1. #!/bin/sh
    fullname=$GEDIT_CURRENT_DOCUMENT_NAME
    name=`echo $fullname | cut -d. -f1`
    suffix=`echo $fullname | cut -d. -f2`
    dir=$GEDIT_CURRENT_DOCUMENT_DIR
    g++ $fullname -o $name
    if [ $? -eq 0 ] ;then
    echo “Successfully Compiled.”;
    gnome-terminal –hide-menubar –working-directory=”$dir” “Terminal-$name” -x bash -c “$dir/$name; echo;echo ‘Press Anykey to continue’;read”
    else echo “Compile Error.\nCheck your code.”;
    fi

发表评论

邮箱地址不会被公开。 必填项已用*标注