题解-Codeforces671D Roads in Yusland

Problem

Codeforces-671D

题意概要：给定一棵 \(n\) 点有根树与 \(m\) 条链，链有费用，保证链端点之间为祖先关系，问至少花费多少费用才能覆盖整棵树（\(n-1\) 条边）

\(n,m\leq 3\times 10^5\)

Solution

有一个线性规划的对偶式子（是从这篇里学习的）：

\(\max\{c^Tx|Ax\leq b\}=\min\{b^Ty|A^Ty\geq c\}\)

（其中 \(x,y,b,c\) 为列向量，\(A\) 为一个矩阵）

其理解可以参照下面这个模型：

第一个式子中：工厂主有 \(n\) 个产品，其中 \(A\) 为这些产品所需原材料的数量，\(x\) 为产品生产数量，\(c\) 为生产一件产品的收益，\(b\) 为原材料数量

第二个式子中：喻同学有 \(m\) 种原材料，其中 \(A^T\) 上述矩阵的转置，\(b,c\) 同理，\(y\) 表示给原材料的定价

第一个式子中的现实意义：工厂主在使用现有原材料的情况下，生产产品所得最大收益

第二个式子中的现实意义：喻同学给工厂主的原材料定价，使得工厂主无论如何都无法获得任何收益，在此情况下尽量使得工厂主支出最少

由于工厂主要最大化自己的收益，而在喻同学的操作下，工厂主已经无法获益，要最大化自己收益（可能为负）只能尽量减少支出

由现实意义可以得出该式子，但严谨证明暂略

回到这题，由于求最小的花费不容易求，使用上述对偶关系进行转换：

原题套用第二个式子：

\(b^T\) : 每条链的费用

\(y\) : 每条链是否选择

\(A^T\) : 每条边是否被每条链覆盖

\(c\) : 每条边至少覆盖一次

求费用最小

对偶成第一个式子：

\(c^T\) : 每条边被覆盖一次

\(x\) : 给每条边构造的权值

\(A\) : 每条链是否覆盖每个点

\(b\) : 每条链的费用

求构造值之和最大

所以原题转化成：给定一棵树，要求给每条边构造一个权值，使得对于每条链而言，链上边权值之和不大于当前链的权值。由于原题保证链一定有祖先关系，可以左偏树贪心

Code

/*

Problem Source : cf-671D

Author : oier_hzy

Time : Nov 19 2019

*/

#include <bits/stdc++.h>

using namespace std;

inline void read(int&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();

}

const int N = 301000;

struct Edge{int v,w,nxt;} a[N*3];

int head[N], Head[N];

int tag[N], cov[N];

int dep[N], len[N];

int rt[N], ls[N], rs[N];

int n,m,_,tot;

long long Ans;

inline void add(int x,int y,int z,int*arr){a[++_].v = y, a[_].w = z, a[_].nxt = arr[x], arr[x] = _;}

struct node{int w, ps;}t[N];

inline void put_tag(int x,int y) {t[x].w += y, tag[x] += y;}

inline void down_tag(int x){

	int&v = tag[x];

	if(!v) return ;

	if(ls[x]) put_tag(ls[x], v);

	if(rs[x]) put_tag(rs[x], v);

	v = 0;

}

int merge(int x,int y){

	if(!x or !y) return x | y;

	down_tag(x), down_tag(y);

	if(t[x].w > t[y].w) swap(x,y);

	rs[x] = merge(rs[x], y);

	if(len[ls[x]] < len[rs[x]]) swap(ls[x], rs[x]);

	len[x] = len[rs[x]] + 1;

	return x;

}

void dfs(int x,int las){

	for(int i=head[x];i;i=a[i].nxt)

		if(a[i].v != las){

			dep[a[i].v] = dep[x] + 1;

			dfs(a[i].v,x);

			rt[x] = merge(rt[x], rt[a[i].v]);

			cov[x] += cov[a[i].v];

		}

	if(x != 1 and !cov[x]) puts("-1"), exit(0);

	for(int i=Head[x];i;i=a[i].nxt){

		t[++tot] = (node) {a[i].w, a[i].v};

		rt[x] = merge(rt[x], tot);

	}

	while(rt[x] and dep[t[rt[x]].ps] >= dep[x]) {

		down_tag(rt[x]);

		rt[x] = merge(ls[rt[x]], rs[rt[x]]);

	}

	Ans += t[rt[x]].w, put_tag(rt[x], -t[rt[x]].w);

}

int main(){

	read(n), read(m);

	int x,y,z;

	for(int i=1;i<n;++i){

		read(x), read(y);

		add(x,y,0,head);

		add(y,x,0,head);

	}

	while(m--){

		read(x), read(y), read(z);

		++cov[x], --cov[y];

		add(x,y,z,Head);

	}

	dfs(1,0);

	printf("%lld\n",Ans);

	return 0;

}

巴特西

题解-Codeforces671D Roads in Yusland

Problem

Solution

Code

最新文章

热门文章