[Codeforces671D]Roads in Yusland

[Codeforces671D]Roads in Yusland

Tags:题解

---

题意

luogu

给定以1为根的一棵树，有\(m\)条直上直下的有代价的链，求选一些链把所有边覆盖的最小代价。若无解输出 -1

\(n\le 3*10^5\)

题解

这题有一些DP做法，这里不再赘述了。

首先你得知道线性规划的对偶。

式子是这样的\(max\{c^Tx|Ax\le b\}=min\{b^Ty|A^Ty\ge c\}\)

强行往上面套（右式）：

• \(c\)为全1列向量，长度为\(m\)
• \(y\)为01列向量，长度为\(m\)，表示每条链选或不选
• \(A^T\)为长\(n-1\)、宽\(m\)的01矩阵，\(A[i][j]\)表示\(i\)这条边在不在第\(j\)条链中
• \(b^T\)为长为\(m\)的行向量，表示选每条链的代价

所以现在的问题就是要构造一个\(x\)使得左式最大。

那我们寻找左式的实际意义：给每条边标记一个权值\(x\)，使得每条链上的边的权值和不超过其代价。

感觉完全不是一个问题了对吧，但是确实他们答案相同。

为方便表述，这条边标记权值\(x\)记为这条边选了\(x\)次。

然后这是一个较为显然的贪心，从深到浅能选则选，用可并堆维护当前点到父亲这条边能选的最多次数。

代码

#include<iostream>

#include<vector>

#define pb push_back

#define lc t[x].ch[0]

#define rc t[x].ch[1]

using namespace std;

const int N=3e5+10;

int n,m,cf[N],rt[N],dep[N],nod;

long long Ans;

vector<int> E[N],St[N];

struct mmp{int x,y,c;}A[N];

struct Heap{int ch[2],val,id,dis,tag;}t[N];

void Put(int x,int k) {t[x].tag+=k;t[x].val+=k;}

void pushdown(int x) {int &v=t[x].tag;if(v) Put(lc,v),Put(rc,v),v=0;}

int Merge(int x,int y)

{

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

	pushdown(x);pushdown(y);

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

	rc=Merge(rc,y);

	if(t[lc].dis<t[rc].dis) swap(lc,rc);

	t[x].dis=t[lc].dis+1;

	return x;

}

int Del(int x) {return Merge(lc,rc);}

void dfs(int x,int fr)

{

	dep[x]=dep[fr]+1;

	for(auto R:E[x])

		if(R!=fr) dfs(R,x),rt[x]=Merge(rt[x],rt[R]),cf[x]+=cf[R];

	if(!cf[x]&&x>1) puts("-1"),exit(0);

	for(auto P:St[x])

		t[++nod].val=A[P].c,t[nod].id=P,rt[x]=Merge(rt[x],nod);

	while(dep[A[t[rt[x]].id].y]>=dep[x]) rt[x]=Del(rt[x]);

	if(rt[x]) Ans+=t[rt[x]].val,Put(rt[x],-t[rt[x]].val);

}

int main()

{

	cin>>n>>m;

	for(int i=1,x,y;i<n;i++)

		scanf("%d%d",&x,&y),E[x].pb(y),E[y].pb(x);

	for(int i=1,x,y,c;i<=m;i++)

	{

		scanf("%d%d%d",&x,&y,&c);

		St[x].pb(i);cf[x]++;cf[y]--;

		A[i]=(mmp){x,y,c};

	}

	dfs(1,0);

	cout<<Ans<<endl;

}