题目描述

先用map把字符串赋予编号,把公园单独设置为编号1,在排序用Kruskal算法把除了编号1以外的人先连接起来.在找出去1号的最短路程,记得累加总路程和能到达的条数.在从剩下的环中去找最长的路,用最长的路减去能到达1号点的最优值,然后断开环的那个点,在累加路程和能到达的条数直到题目要求的条数就ok了.

样例

10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3

算法1

(暴力枚举) $O(n^2)$

我自己的理解

时间复杂度分析：O(NlogN)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,o,k,tot,sum;
map<string,int> q;
int lj[110][110];//邻接
int l1[110];//可以连的线路
int ll[110];//可以连的线路的坐标
int fx[110];
bool nz[110][110];//可以去1号的点为真
int zuidian;
struct asd//判断最终可不可以走
{
    int w;
    int l;
    int r;
}pd[110];
struct dsa
{
    int x;
    int y;
    int z;
}csz[100010];
bool bll(dsa a,dsa b)//以z从小到大排
{
    return a.z<b.z;
}
int da(int a)//取a的老大
{
    if(a==fx[a])
    {
        return a;
    }
    return fx[a]=da(fx[a]);
}
void com()
{
    sort(csz+1,csz+1+n,bll);//先给结构体排个序
    for(int i=1;i<=o;i++)//初始化自己都是自己的老大
    {
        fx[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int a=csz[i].x,b=csz[i].y,c=csz[i].z;
        int fa=da(a);//取两点的老大
        int fb=da(b);
        if(fa==1||fb==1)//跳过1号
        {
            continue;//那么直接优化跳过
        }
        if(fa!=fb)//跳过自己到自己
        {
            fx[fa]=fb;//先把除了1号以外的树连接起来
            tot=tot+c;//路程累加
            nz[a][b]=1;//把两个位置标记为可以走
            nz[b][a]=1;
        }
    }
}
void dfs(int fl,int pl)//找出不能去1号点的最长路程
{
    for(int i=2;i<=o;i++)//跳过一号点
    {
        if(i==pl||!nz[fl][i])//如果不可以走就跳过
        {
            continue;
        }
        if(pd[i].w==-1)//如果值没有变过,说明这些路是到不了1号点的,从中找最长的路程
        {
            if(pd[fl].w>lj[fl][i])
            {
                pd[i]=pd[fl];
            }
            else
            {
                pd[i].w=lj[fl][i];
                pd[i].l=fl;
                pd[i].r=i;
            }
        }
        dfs(i,fl);
    }
}
int main()
{
    memset(lj,0x3f,sizeof(lj));//初始化
    memset(l1,0x3f,sizeof(l1));
    cin>>n;
    o++;
    q["Park"]=o;//把公园设置为编号1,当特殊编号使用
    for(int i=1;i<=n;i++)
    {
        string a,b;
        int c;
        cin>>a>>b>>c;
        if(!q[a])//给每一个没有编号的人建立编号,用map与它们关联
        {
            o++;
            q[a]=o;
        }
        if(!q[b])
        {
            o++;
            q[b]=o;
        }
        int ans1=q[a];//在把位置存入结构体中
        int ans2=q[b];
        csz[i].x=ans1;
        csz[i].y=ans2;
        csz[i].z=c;
        lj[ans1][ans2]=min(lj[ans1][ans2],c);//在邻接矩阵中存最小的路程
        lj[ans2][ans1]=min(lj[ans1][ans2],c);//无向图
    }
    cin>>k;//到Park的车子只能有k个
    com();//这里进去把除了1号以外的树连接起来
    for(int i=2;i<=o;i++)//从2开始找,跳过1号,寻找去1号的路
    {
        if(lj[1][i]<0x3f)//寻找邻接矩阵中的第一行
        {
            int a=da(i);//因为前面已经把树都连接起来了,直接找老大就好了
            if(l1[a]>lj[1][i])//给第一行中老大和自己(i)比大小
            {
                l1[a]=lj[1][i];//老大取小(i)的值
                ll[a]=i;//ll中存的是老大取那一个小(i)的关系
            }
        }
    }
    for(int i=2;i<=o;i++)
    {
        if(l1[i]<0x3f)//统计有几条路是可以去1号的
        {
            sum++;//可以去的直接累加起来
            nz[1][ll[i]]=1;//把两位置都标记可以走
            nz[ll[i]][1]=1;
            tot=tot+lj[1][ll[i]];//累加路程
        }
    }
    for(int i=sum+1;i<=k;i++)//到Park的车子只能有k个
    {
        memset(pd,-1,sizeof(pd));//初始化结构体
        pd[1].w=-0x3f;//1号的位置赋值为最小
        for(int j=2;j<=o;j++)//跳过1号
        {
            if(nz[1][j])//如果还有路可以走
            {
                pd[j].w=-0x3f;//就赋值为最小
            }
        }
        dfs(1,-1);//找最长的路程
        int lc=0x3f;
        for(int j=2;j<=o;j++)
        {
            if(lc>lj[1][j]-pd[j].w)//判断选最长的路程是赚了还是亏了
            {
                lc=lj[1][j]-pd[j].w;//选最赚的路程
                zuidian=j;//储存最赚的路程是那一条
            }
        }
        if(lc>=0)
        {
            break;//如果没有最赚的路程就返回
        }
        nz[1][zuidian]=1;//标记为可以走
        nz[zuidian][1]=1;
        nz[pd[zuidian].l][pd[zuidian].r]=1;//把路线断开
        nz[pd[zuidian].r][pd[zuidian].l]=0;
        tot=tot+lc;//累加上赚了的路程
    }
    cout<<"Total miles driven: "<<tot;
    return 0;
}
换一种变量写
#include<bits/stdc++.h>
using namespace std;
const int M=55;
int n,m,k,ans;
int ee[M][M];
bool in[M][M];//可以去1号的点为真
int fa[M];
int tot;
struct edge
{
    int h;
    int t;
    int w;
}e[10010];
struct edges
{
    int w;
    int l;
    int r;
}dp[M];
map<string,int> vis;
int mintree[M],tminpoint[M];
int num=0,minpoint,point;
bool cmp(edge x,edge y)//以w从小到大排
{
    return x.w<y.w;
}
int get(int x)//取x的老大
{
    if(x==fa[x])
    {
        return x;
    }
    return fa[x]=get(fa[x]);
}
void Kruskal()
{
    sort(e+1,e+tot+1,cmp);//先给结构体排个序
    for(int i=1;i<=m;i++)
    {
        fa[i]=i;//初始化自己都是自己的老大
    }
    for(int i=1;i<=tot;i++)
    {
        int x=e[i].h,y=e[i].t,z=e[i].w;
        int fx=get(x);//取两点的老大
        int fy=get(y);
        if(fx==1||fy==1)//跳过1号
        {
            continue;//那么直接优化跳过
        }
        if(fx!=fy)//跳过自己到自己
        {
            fa[fx]=fy;//先把除了1号以外的树连接起来
            ans=ans+z;//路程累加
            in[x][y]=1;//把两个位置标记为可以走
            in[y][x]=1;
        }
    }
}
void dfs(int fl,int pl)//找出不能去1号点的最长路程
{
    for(int i=2;i<=m;i++)//跳过一号点
    {
        if(i==pl||!in[fl][i])//如果不可以走就跳过
        {
            continue;
        }
        if(dp[i].w==-1)//如果值没有变过,说明这些路是到不了1号点的,从中找最长的路程
        {
            if(dp[fl].w>ee[fl][i])
            {
                dp[i]=dp[fl];
            }
            else
            {
                dp[i].w=ee[fl][i];
                dp[i].l=fl;
                dp[i].r=i;
            }
        }
        dfs(i,fl);
    }
}
int main()
{
    memset(ee,0x3f,sizeof(ee));//初始化
    memset(mintree,0x3f,sizeof(mintree));
    cin>>n;
    m++;//把公园设置为编号1,当特殊编号使用
    vis["Park"]=m;
    for(int i=1;i<=n;i++)
    {
        string x,y;
        int z;
        cin>>x>>y>>z;
        if(!vis[x])//给每一个没有编号的人建立编号,用map与它们关联
        {
            m++;
            vis[x]=m;
        }
        if(!vis[y])
        {
            m++;
            vis[y]=m;
        }
        int nx=vis[x];//在把位置存入结构体中
        int ny=vis[y];
        e[++tot].h=nx;
        e[tot].t=ny;
        e[tot].w=z;
        ee[nx][ny]=min(ee[nx][ny],z);//在邻接矩阵中存最小的路程
        ee[ny][nx]=min(ee[nx][ny],z);//无向图
    }
    cin>>k;//到Park的车子只能有k个
    Kruskal();//这里进去把除了1号以外的树连接起来
    for(int i=2;i<=m;i++)//从2开始找,跳过1号,寻找去1号的路
    {
        if(ee[1][i]<0x3f)//寻找邻接矩阵中的第一行
        {
            int which=get(i);//因为前面已经把树都连接起来了,直接找老大就好了
            if(mintree[which]>ee[1][i])//给第一行中老大和自己(i)比大小
            {
                mintree[which]=ee[1][i];//老大取小(i)的值
                tminpoint[which]=i;//tminpoint中存的是老大取那一个小(i)的关系
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(mintree[i]<0x3f)//统计有几条路是可以去1号的
        {
            num++;//可以去的直接累加起来
            in[1][tminpoint[i]]=1;//把两位置都标记可以走
            in[tminpoint[i]][1]=1;
            ans=ans+ee[1][tminpoint[i]];//累加路程
        }
    }
    for(int i=num+1;i<=k;i++)//到Park的车子只能有k个
    {
        memset(dp,-1,sizeof(dp));//初始化结构体
        dp[1].w=-0x3f;//1号的位置赋值为最小
        for(int j=2;j<=m;j++)//跳过1号
        {
            if(in[1][j])//如果还有路可以走
            {
                dp[j].w=-0x3f;//就赋值为最小
            }
        }
        dfs(1,-1);//找最长的路程
        minpoint=0x3f;
        for(int j=2;j<=m;j++)
        {
            if(minpoint>ee[1][j]-dp[j].w)//判断选最长的路程是赚了还是亏了
            {
                minpoint=ee[1][j]-dp[j].w;//选最赚的路程
                point=j;//储存最赚的路程是那一条
            }
        }
        if(minpoint>=0)
        {
            break;//如果没有最赚的路程就返回
        }
        in[1][point]=1;//标记为可以走
        in[point][1]=1;
        in[dp[point].l][dp[point].r]=1;//把路线断开
        in[dp[point].r][dp[point].l]=0;
        ans=ans+minpoint;//累加上赚了的路程
    }
    cout<<"Total miles driven: "<<ans;
    return 0;
}