Invatation

题意:

有A个男生和B个女生(A,B<=10⁹)。

已知n(n<=10⁵)对朋友关系。

每对关系描述编号在一个区间中的男生和编号在另一个区间中的女生属于一个朋友圈。

每个朋友圈有一个好感度。

现在有个男生C要邀请所有人参加派对。

每个人只能被邀请1次，被同属于一个朋友圈的人邀请会得到对应好感度的奖励。

最大化得到的奖励。

分析:

直接离散化后对线段做kruskal求最大生成树。。。

#include <set>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define l first
#define r second
#define rep(i,a,b) for(int i=a;i<b;++i)
using namespace std;

#define g() getchar()
template<class Q>inline void Scan(Q&x){
	char c; int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

const int MAXN=1e5+5;

typedef long long ll;

int A,B,n;

typedef pair<int,int>pr;

pr a[MAXN],b[MAXN];

int cnt,w[MAXN],id[MAXN];

inline bool cmp(int a,int b){
	return w[a]>w[b];
}

int ta,ah[MAXN*6],tb,bh[MAXN*6];

int f[MAXN*12],sz[MAXN*12];

int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
inline void merge(int x,int y){
	if(sz[x]<sz[y])swap(x,y);
	sz[y]+=sz[x],f[x]=y;
}

ll ans;

set<int>iru,neko;

inline void Addh(int*a,int&t,int x){
	a[++t]=x-1,a[++t]=x,a[++t]=x+1;
}
inline int find(int*a,int n,int x){
	return lower_bound(a+1,a+1+n,x)-a;
}	

inline void Init(){
	Scan(A),Scan(B),Scan(n);
	Scan(n);
	rep(i,1,n+1){
		id[i]=i;
		Scan(a[i].l),Scan(a[i].r);
		Scan(b[i].l),Scan(b[i].r);
		Scan(w[i]);
		Addh(ah,ta,a[i].l),Addh(ah,ta,a[i].r);
		Addh(bh,tb,b[i].l),Addh(bh,tb,b[i].r);
	}
	sort(ah+1,ah+1+ta),ta=unique(ah+1,ah+1+ta)-(ah+1);
	sort(bh+1,bh+1+tb),tb=unique(bh+1,bh+1+tb)-(bh+1);
	rep(i,1,ta+1){
		f[i]=i,sz[i]=1;
		iru.insert(i);
	}
	iru.insert(ta+1);
	rep(i,1,tb+1){
		f[i+ta]=i+ta,sz[i+ta]=1;
		neko.insert(i);
	}
	neko.insert(tb+1);
	sort(id+1,id+1+n,cmp);
}

inline void Union(set<int>&s,int*a,int l,int r,int t,int w){
	set<int>::iterator it;
	while(!s.empty()){
		it=s.upper_bound(l);
		if(*it>r)return;
		int x=find(l+t),y=find(*it+t);
		if(x!=y){
			int siz=a[*it]-a[*it-1];
			cnt+=siz;
			ans+=1ll*siz*w;
			merge(x,y);
		}
		s.erase(it);
	}
}

inline void Solve(){
	rep(cur,1,n+1){
		int i=id[cur];
		int l1=find(ah,ta,a[i].l),r1=find(ah,ta,a[i].r);
		Union(iru,ah,l1,r1,0,w[i]);
		int l2=find(bh,tb,b[i].l),r2=find(bh,tb,b[i].r);
		Union(neko,bh,l2,r2,ta,w[i]);
		int x=find(l1),y=find(l2+ta);
		if(x!=y){
			++cnt;
			ans+=w[i];
			merge(x,y);
		}
	}
	printf("%I64d\n",cnt<A+B -1?-1:ans);
}

int main(){
	freopen("invitation.in","r",stdin);
	freopen("invitation.out","w",stdout);
	Init(); Solve(); return 0;
}