国家集训队2 Tree I

wjh15101051's space

卧薪尝胆，厚积薄发。

国家集训队2 Tree I

Date: Sat Sep 15 21:19:35 CST 2018

In Category: NoCategory

Description：

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 $need$ 条白色边的生成树。

$1\le n \le 50000,1\le m \le 100000$

Solution：

$DP$ 凸优化，给白边二分一个偏移量 $d$ ，然后用 $kruskal$ 求最小生成树判断是否有 $need$ 条白边，然后调整二分的边界即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,ned;

#define MAXM 100010

struct edge

{

	int u,v,val,col;

}e[MAXM];

bool cmp_val(edge a,edge b){return (a.val == b.val ? a.col < b.col : a.val < b.val);}

#define MAXN 50010

int f[MAXN];

int find(int x){return (f[x] == x ? x : f[x] = find(f[x]));}

int ans;

int query(int k)

{

	ans = 0;

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

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

		if(e[i].col == 0)

			e[i].val += k;

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

	int res = 0;

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

	{

		int p = find(e[i].u),q = find(e[i].v);

		if(p == q)continue;

		f[p] = q;

		if(e[i].col == 0)++res;

		ans += e[i].val;

	}

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

		if(e[i].col == 0)

			e[i].val -= k;

	return res;

}

int main()

{

	scanf("%d%d%d",&n,&m,&ned);

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

	{

		scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].val,&e[i].col);

		++e[i].u;++e[i].v;

	}

	int l = -100,r = 100,mid;

	while(l < r)

	{

		mid = ((l + r + 1) / 2);//cout << mid << endl;

		if(query(mid) >= ned)l = mid;

		else r = mid - 1;

	}//cout << l << endl;

	query(l);

	cout << ans - ned * l << endl;

	return 0;

}

In tag: DP-DP凸优化

wjh15101051