2020 ICPC Asia Taipei-Hsinchu Regional Problem H Optimization for UltraNet (二分,最小生成树,dsu计数)

题意:给你一张图,要你去边,使其成为一个边数为\(n-1\)的树,同时要求树的最小边权最大,如果最小边权最大的情况有多种,那么要求总边权最小.求生成树后的所有简单路径上的最小边权和.
题解:刚开始想写最大生成树的,但是很明显不能满足总边权最小的要求.所以这里我们可以用二分,二分最小边权的值,然后再去跑kruskal看是否能构造成一颗树,这样的话我们就能得出满足题目条件的树.之后我们再将边权从大到小排序来枚举,用并查集维护连通块,假如两个块不连通,因为此时的边权是目前最小的,简单路径数是两个连通块数量的乘积,很显然贡献为包含这条边的简单路径数*边权.
代码:

#include <bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

#define rep(a,b,c) for(int a=b;a<=c;++a)

#define per(a,b,c) for(int a=b;a>=c;--a)

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,m;

int p[N],sz[N];

struct misaka{

	int a,b;

	int val;

	bool operator < (const misaka & mikoto) const{

		return val<mikoto.val;

	}

}e[N];

vector<misaka> v;

int find(int x){

	if(p[x]!=x) p[x]=find(p[x]);

	return p[x];

}

bool check(int x){

	if(m-x+1<n-1) return false;

	rep(i,1,n) p[i]=i;

	int cnt=0;

	rep(i,x,m){

		int fa=find(e[i].a);

		int fb=find(e[i].b);

		if(fa!=fb){

			p[fa]=fb;

			cnt++;

		}

	}

	return cnt==n-1;

}

void build(int x){

	int cnt=0;

	rep(i,1,n) p[i]=i;

	rep(i,x,m){

		int a=e[i].a;

		int b=e[i].b;

		int val=e[i].val;

		int fa=find(a);

		int fb=find(b);

		if(fa==fb) continue;

		p[fa]=fb;

		v.pb({a,b,val});

		//cout<<a<<' '<<b<<' '<<val<<'\n';

		cnt++;

		if(cnt==n-1) break;

	}

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n>>m;

	rep(i,1,n){

		p[i]=i;

		sz[i]=1;

	}

	rep(i,1,m){

		cin>>e[i].a>>e[i].b;

		cin>>e[i].val;

	}

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

	int l=1,r=m;

	while(l<r){

		int mid=(l+r+1)>>1;

		if(check(mid)) l=mid;

		else r=mid-1;

	}

	build(l);

	reverse(v.begin(),v.end());

	ll ans=0;

	int cnt=1;

	rep(i,1,n) p[i]=i;

	for(auto w:v){

		int fa=find(w.a);

		int fb=find(w.b);

		p[fa]=fb;

		ans+=1ll*sz[fa]*sz[fb]*w.val;

		sz[fb]+=sz[fa];

	}

	cout<<ans<<'\n';

    return 0;

}

巴特西

2020 ICPC Asia Taipei-Hsinchu Regional Problem H Optimization for UltraNet (二分,最小生成树,dsu计数)

最新文章

热门文章