bzoj2395: [Balkan 2011]Timeismoney

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2395

思路：与bzoj3571类似的思想，只是内部是kruskal而已

其实数据范围最大是会爆int的，然而并没有爆

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=210,maxm=10010;
using namespace std;
struct Edge{int x,y,a,b,v;}E[maxm];
struct poi{int x,y;}L,R,ans;
bool operator <(Edge a,Edge b){return a.v<b.v;}
poi operator -(poi a,poi b){return (poi){a.x-b.x,a.y-b.y};}
int operator *(poi a,poi b){return a.x*b.y-a.y*b.x;}
bool operator <(poi a,poi b){
	int va=a.x*a.y,vb=b.x*b.y;
	return va!=vb?va<vb:a.x<b.x;
}
bool operator ==(poi a,poi b){return a.x==b.x&&a.y==b.y;}
poi min(poi a,poi b){return a<b?a:b;}
int n,m,fa[maxn];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
poi kruskal(){
	for (int i=1;i<=n;i++) fa[i]=i;
	sort(E+1,E+1+m);poi res=(poi){0,0};
	for (int i=1;i<=m;i++){
		int x=E[i].x,y=E[i].y;
		if (getfa(x)!=getfa(y)) fa[getfa(x)]=getfa(y),res.x+=E[i].a,res.y+=E[i].b;
	}
	ans=min(ans,res);
	return res;
}

void solve(poi l,poi r){
	for (int i=1;i<=m;i++) E[i].v=(l.y-r.y)*E[i].a+(r.x-l.x)*E[i].b;
	poi mid=kruskal();//printf("l%d %d mid%d %d r%d %d
",l.x,l.y,mid.x,mid.y,r.x,r.y);
	if ((r-l)*(mid-l)<0) solve(l,mid),solve(mid,r);
}

int main(){
	scanf("%d%d",&n,&m);ans=(poi){30000,30000};
	for (int i=1;i<=m;i++) scanf("%d%d%d%d",&E[i].x,&E[i].y,&E[i].a,&E[i].b),E[i].x++,E[i].y++;
	for (int i=1;i<=m;i++) E[i].v=E[i].a;L=kruskal();
	for (int i=1;i<=m;i++) E[i].v=E[i].b;R=kruskal();
	solve(L,R),printf("%d %d
",ans.x,ans.y);
	return 0;
}