[APIO2013]道路费用

标签：因此   复杂   +=   决定   大量   ++   ems   参与者   设定   

题目描述

幸福国度可以用 N 个城镇（用 1 到 N 编号）构成的集合来描述，这些城镇 最开始由 M 条双向道路（用 1 到 M 编号）连接。城镇 1 是中央城镇。保证一个 人从城镇 1 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是 收费道路，道路 i 的使用者必须向道路的主人支付 ci分钱的费用。已知所有的这 些ci是互不相等的。最近有K条新道路建成，这些道路都属于亿万富豪Mr. Greedy。 Mr. Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣 布这些费用。

两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这 些道路游行并前往中央城镇。共计 pj个参与者将从城镇 j 出发前往中央城镇。这 些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一 天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就 是 Mr. Greedy。同样根据这个习俗，Mr. Greedy 选出的这个道路集合必须使所有 选出道路的费用之和最小，并且仍要保证任何人可以从城镇 j 前往城镇 1（因此， 这些选出的道路来自将费用作为相应边边权的“最小生成树”）。如果有多个这样 的道路集合，Mr. Greedy 可以选其中的任何一个，只要满足费用和是最小的。

Mr. Greedy 很明确地知道，他从 K 条新道路中获得的收入不只是与费用有 关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 p 个人经过道路 i，道路 i 产生的收入为 ci p 的积。注意 Mr. Greedy 只能从新道路 收取费用，因为原来的道路都不属于他。

Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收 入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路 （将在嘉年华的前一天公布），使得他在 K 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序 来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。

题解

我们需要让这k条边的代价最大。

看到k很小，可以想到枚举每条边的选择情况，但如果直接每次跑一遍最小生成树会使复杂度变得很高。

首先我们把这\(k\)条边先加进去，然后再对其他边跑最小生成树，那么此时加进去的边一定是必须在最后的生成树里的。

那么我们把这些边提前加进去，这样会形成\(k+1\)个联通块，我们把这些联通块看做点，那么点数的级别就变成了\(O(K)\)的。

然后我们还发现有些边是没用的，我们先把联通块缩点，然后用\(kruskal\)尝试填加其他边，那么我们只会填加\(k\)条边，可以发现，此时还没有添加进去的边是没有用的，这些边就是可能会加进去的边，这样边数也是\(O(K)\)的了。

对于新边的权值的设定，就是所有跨过它的边的权值最小值。

然后这道题就变成大模拟了。。

代码

#include
#define N 100009
#define M 300009
#define K 22
#define inf 2e9
using namespace std;
typedef long long ll;
int f[N],n,m,k,l[N],r[N],dep[N],be[N],tot,num[N],tong[N],ma[K],mx[N],ji[K];
ll size[N],w[N],sum[N],ans;
bool vis[N];
int head[K],tott; 
struct edge{
    int n,to,l;
}e[Kdep[yy])mx[xx]=min(mx[xx],b[ji[j]].w),xx=f[xx];
            while(xx!=yy){
                mx[xx]=min(mx[xx],b[ji[j]].w);
                mx[yy]=min(mx[yy],b[ji[j]].w);
                xx=f[xx];yy=f[yy];
            }
        }
        ans=max(ans,dfs(zh(1),0));
    }
    printf("%lld\n",ans);
    return 0;
}

[APIO2013]道路费用

标签：因此   复杂   +=   决定   大量   ++   ems   参与者   设定   

原文地址：https://www.cnblogs.com/ZH-comld/p/10804256.html