POJ1629:picnic planning

题目描述

矮人虽小却喜欢乘坐巨大的轿车，轿车大到可以装下无论多少矮人。某天，N(N≤20)个矮人打算到野外聚餐。为了

集中到聚餐地点，矮人A 有以下两种选择

1）开车到矮人B家中，留下自己的轿车在矮人B家，然后乘坐B的轿车同行

2）直接开车到聚餐地点，并将车停放在聚餐地。虽然矮人的家很大，可以停放无数量轿车，但是聚餐地点却最多只能停放K辆轿车。

现在给你一张加权无向图，它描述了N个矮人的家和聚餐地点，要你求出所有矮人开车的最短总路程。

输入格式

第一行是整数M，接下来M行描述了M条道路。

每行形式如同：S1 S2 x，S1和S2均是由字母组成长度不超过20的字符串

(特别地，当该字符串为”Park”时表示聚餐地点)，x是整数，表示从S1到S2的距离。

最后一行包含单独的整数k.

输出格式

仅一行，形式如同：

Total miles driven: xxx

xxx是整数，表示最短总路程。

设Park为1节点。

先不考虑1节点，我们求出去掉1节点之后的图的最小生成树森林。设森林包含x棵树，那么我们从每棵树上都找出一条最短的连向1节点的边连起来。

然后我们可以再给1节点加上k-x条边。扫描1节点连接的所有还没被加入生成树的边，设其边长为p，两个端点为u,v，我们求出u和v在生成树上的路径中的最大边，设其边长为q。如果p-q<0，那么把q删去，把p加上。直到扫描完所有边或者加了k-x条边时，我们便得到了题目所求的生成树。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<map>

#define maxn 31

using namespace std;

struct edge{

    int u,v,w;

    bool operator<(const edge &e)const{ return w<e.w; }

}e[maxn*maxn],dp[maxn];

int key[maxn],minedge[maxn];

int fa[maxn],g[maxn][maxn];

bool tree[maxn][maxn];

int n,m,k,ans;

map<string,int> id;

inline int read(){

    register int x(0),f(1); register char c(getchar());

    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }

    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

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

inline void kruskal(){

    sort(e+1,e+1+m);

    for(register int i=1;i<=n;i++) fa[i]=i;

    for(register int i=1;i<=m;i++){

        int u=e[i].u,v=e[i].v,w=e[i].w;

        if(u==1||v==1||get(u)==get(v)) continue;

        fa[get(u)]=get(v),tree[u][v]=tree[v][u]=true;

        ans+=w;

    }

}

void dfs(int u,int pre){

    for(register int i=2;i<=n;i++) if(tree[u][i]){

        if(i==pre) continue;

        if(dp[i].w==-1){

            if(dp[u].w>g[u][i]) dp[i]=dp[u];

            else{

                dp[i].w=g[u][i],dp[i].u=u,dp[i].v=i;

            }

        }

        dfs(i,u);

    }

}

inline void solve(){

    register int cnt=0;

    for(register int i=2;i<=n;i++) if(g[i][1]!=0x3f3f3f3f){

        int col=get(i);

        if(g[i][1]<minedge[col]) minedge[col]=g[i][1],key[col]=i;

    }

    for(register int i=1;i<=n;i++) if(minedge[i]!=0x3f3f3f3f){

        cnt++,tree[key[i]][1]=tree[1][key[i]]=true;

        ans+=g[1][key[i]];

    }

    for(register int i=cnt+1;i<=k;i++){

        memset(dp,-1,sizeof dp);

        dp[1].w=-0x3f3f3f3f;

        for(register int j=2;j<=n;j++) if(tree[1][j]) dp[j].w=-0x3f3f3f3f;

        dfs(1,1);

        int d,mini=0x3f3f3f3f;

        for(register int j=2;j<=n;j++) if(mini>g[1][j]-dp[j].w){

            mini=g[1][j]-dp[j].w,d=j;

        }

        if(mini>=0) continue;

        tree[1][d]=tree[d][1]=true,tree[dp[d].u][dp[d].v]=tree[dp[d].v][dp[d].u]=false;

        ans+=mini;

    }

}

int main(){

    memset(g,0x3f,sizeof g),memset(minedge,0x3f,sizeof minedge);

    m=read(),id["Park"]=++n;

    for(register int i=1;i<=m;i++){

        string a,b; cin>>a>>b;

        if(!id[a]) id[a]=++n;

        if(!id[b]) id[b]=++n;

        e[i].u=id[a],e[i].v=id[b],e[i].w=read();

        g[e[i].u][e[i].v]=g[e[i].v][e[i].u]=min(g[e[i].u][e[i].v],e[i].w);

    }

    k=read();

    kruskal(),solve();

    printf("Total miles driven: %d\n", ans);

    return 0;

}

巴特西

POJ1629:picnic planning

题目描述

矮人虽小却喜欢乘坐巨大的轿车，轿车大到可以装下无论多少矮人。某天，N(N≤20)个矮人打算到野外聚餐。为了

集中到聚餐地点，矮人A 有以下两种选择

1）开车到矮人B家中，留下自己的轿车在矮人B家，然后乘坐B的轿车同行

2）直接开车到聚餐地点，并将车停放在聚餐地。虽然矮人的家很大，可以停放无数量轿车，但是聚餐地点却最多只能停放K辆轿车。

现在给你一张加权无向图，它描述了N个矮人的家和聚餐地点，要你求出所有矮人开车的最短总路程。

输入格式

第一行是整数M，接下来M行描述了M条道路。

每行形式如同：S1 S2 x，S1和S2均是由字母组成长度不超过20的字符串

(特别地，当该字符串为”Park”时表示聚餐地点)，x是整数，表示从S1到S2的距离。

最后一行包含单独的整数k.

输出格式

仅一行，形式如同：

Total miles driven: xxx

xxx是整数，表示最短总路程。

设Park为1节点。

先不考虑1节点，我们求出去掉1节点之后的图的最小生成树森林。设森林包含x棵树，那么我们从每棵树上都找出一条最短的连向1节点的边连起来。

最新文章

热门文章