N个点M条边的无向连通图, 边带权且权值各不相同, 点也带权. 现有另外K条权值待定的边 (端点已知). 确定它们的权值, 使得: 取该图的某棵最小生成树, 每个点沿树边走向1号点, 点权与途经的新边边权之积的总和 (收益) 最大. 输出这个最大的和. (N≤10^5, M≤3*10^5 且 K≤20) 读了题之后有点懵逼, 不知从何入手.
发现自己并不会写K>1时的暴力......这个暴力算是正解的基础吧......所以懵逼的时候可以想想怎么暴力.
考虑增量法构造最小生成树的算法: 设新添加一条边(u,v), 权值为w. 1. 若u,v未连通, 把它们连起来. 2. 若u,v已连通, 设path(u,v)上的最大边权为mx, 如果mx>w, 删掉mx对应的边, 添加(u,v), 否则忽略(u,v).
怎样保证某些 (不形成环的) 边同时在某棵最小生成树里呢? 先添加它们, 然后, 确保情形(2)中, 如果mx对应这些边中的一条, 总有mx≤w. 利用这个原理, 也就可以给它们赋值了.
暴力: 2^K枚举出现在某棵最小生成树里的边, 确定它们的权值, DFS求收益. 时间复杂度O(2^K (K+N(M+N))).
原图边权各不相同, 保证了枚举出来的每种情况, 最小生成树的形态是唯一确定的.
K≤20, 枚举的思路可以保留. 注意到原来的M条边中, 有一些是必选的. 令K条边的权值为-inf求一遍最小生成树, M条边在树中的那些即为必选者. 证明: 考虑Kruskal. 前i条边全部添加后的连通性和前i条边的生成森林的连通性相同, 所以, 如果第(i+1)条边连接连通块x,y, 去掉前i条边中的一些, 此时x,y将仍不连通, 第(i+1)条边将被选中.
将M条边中的必选边加入, 一个连通块缩成一个点, 得到一张点数不多于(K+1)的新图. 令新图中的点权为原图连通块的点权和. 新图的生成树的收益可以像在原图上一样求.
有效地减少了点数, 但边仍然很多. 只考虑原图的M条边, 暂不考虑那权值待定的K条边. 首先, 为了进行暴力, 重边只用取权值最小的那条. 进一步地, 只用取新图最小生成树上的边: 如果最小生成树唯一, 使用增量法构造, 边的顺序是无关紧要的; 后面的步骤不用考虑原来就被踢掉的边. 也就是说, 一些边原来就不在最小生成树上, 给图加一些边 (保证最小生成树唯一), 它们仍然不会出现在最小生成树中.
至此, 得到一张点数不超过(K+1), 边数不超过K的新图, 在上面跑暴力, 问题就解决了. 回顾一下, 整个算法步骤如下: - 令K条边的权值为-inf跑一遍最小生成树, 求出M条边中的必选者. - 将必选边形成的每个连通块缩成一个点. - 只使用那M条边, 在缩点后的图上跑最小生成树, 扔掉所有非树边. - 2^K枚举出现在最小生成树里的边, 确定权值, 求出收益.
时间复杂度O(Mlg M + N + 2^K K^2) (视并查集的时间复杂度为常数).
即便时限3s, 还是有点卡. 实现的时候避免使用STL; 在树上找两点间路径不要DFS, 而是转有根树后比较两者深度向上跳.
有一个数组开小了, 半天没拍出来; 拿不开O2的程序和开O2的程序相互对拍的确更有可能发现这类错误. 另一个发现是, 对拍最好覆盖所有数据范围.
typedef long long ll;
const int N = 1e5, M = 3e5, K = 20;
struct Edge {
int x, y, w;
bool operator<(const Edge& o) const
{
return w < o.w;
}
} E[K+M];
int f[N+1], rk[N+1];
int F(int x)
{
return f[x] ? f[x] = F(f[x]) : x;
}
inline void reset(int n)
{
fill_n(f+1, n, 0);
fill_n(rk+1, n, 0);
}
inline void merge(int rx, int ry)
{
if (rx == ry) return;
if (rk[rx] < rk[ry]) swap(rx, ry);
f[ry] = rx;
rk[rx] += rk[rx] == rk[ry];
}
void kruskal(int n, int l, int r, int ans[])
{
int c = 0;
reset(n);
rep (i, l, r) {
int x = F(E[i].x), y = F(E[i].y);
if (x != y) {
merge(x, y);
ans[c++] = i;
if (c == n-1) break;
}
}
}
int n, m, k, cnt, id[N+1], p[N+1], adj[K+2], dep[K+2], fa[K+2];
ll sum[K+2], ss[K+2];
bool b[K+2], used[2*K];
struct List {
int to, nxt;
bool b;
} L[2*K+1];
int ptr = 1;
inline void add(int x, int y, bool b)
{
L[ptr] = (List){y, adj[x], b};
adj[x] = ptr++;
}
void dfs(int u, int p)
{
ss[u] = sum[u];
for (int i = adj[u]; i; i = L[i].nxt) {
int v = L[i].to;
if (v == p) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
b[v] = L[i].b;
dfs(v, u);
ss[u] += ss[v];
}
}
inline void update(int& x, int w, ll& ans)
{
if (!b[x]) return;
ans += w * ss[x];
b[x] = false;
}
ll cal(int s)
{
ptr = 1;
fill_n(adj+1, cnt, 0);
reset(cnt);
rep (i, 0, k) if (s & (1<<i)) {
int x = E[i].x, y = E[i].y, rx = F(x), ry = F(y);
if (rx == ry) return 0;
add(x, y, true);
add(y, x, true);
merge(rx, ry);
}
rep (i, k, k+cnt-1) {
int x = E[i].x, y = E[i].y, rx = F(x), ry = F(y);
if (rx != ry) {
add(x, y, false);
add(y, x, false);
merge(rx, ry);
used[i] = false;
} else {
used[i] = true;
}
}
dfs(1, 0);
ll ans = 0;
rep (i, k, k+cnt-1) if (used[i]) {
int x = E[i].x, y = E[i].y, w = E[i].w;
if (dep[y] < dep[x]) swap(x, y);
while (dep[y] != dep[x]) {
update(y, w, ans);
y = fa[y];
}
while (x != y) {
update(x, w, ans);
update(y, w, ans);
x = fa[x];
y = fa[y];
}
}
return ans;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
rep (i, k, k+m)
scanf("%d%d%d", &E[i].x, &E[i].y, &E[i].w);
rep (i, 0, k)
scanf("%d%d", &E[i].x, &E[i].y);
rep (i, 1, n+1)
scanf("%d", p+i);
sort(E+k, E+k+m);
static int v[N-1];
kruskal(n, 0, k+m, v);
reset(n);
rep (i, 0, n-1) {
if (v[i] >= k)
merge(F(E[v[i]].x), F(E[v[i]].y));
}
rep (i, 1, n+1) {
int j = F(i);
if (!id[j]) id[j] = ++cnt;
sum[id[i] = id[j]] += p[i];
}
rep (i, 0, k+m) {
E[i].x = id[E[i].x];
E[i].y = id[E[i].y];
}
kruskal(cnt, k, k+m, v);
rep (i, 0, cnt-1)
E[k+i] = E[v[i]];
ll ans = 0;
rep (s, 1, 1<<k)
ans = max(ans, cal(s));
printf("%lld\n", ans);
return 0;
}