记录编号	285833	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	Time is Money	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	2.339 s
提交时间	2016-07-25 08:39:21	内存使用	0.62 MiB

#include <algorithm> 
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=210;
const int maxm=10010;
int fa[maxn],a[maxm],b[maxm];
int u[maxm],v[maxm],n,m;

struct Node{
	int x,y,z,id;
	Node(int a=0,int b=0,int c=0,int d=0){
		x=a;y=b;z=c;id=d;
	}
	friend bool operator <(Node a,Node b){
		return a.z<b.z;
	}
}p[maxm];

struct Point{
	int x,y;
	Point(int a=0,int b=0){
		x=a;y=b;
	}
	friend bool operator ==(Point a,Point b){
		return a.x==b.x&&a.y==b.y;
	}
}lo,hi;

int Find(int x){
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}

Point Get_Ans(){
	sort(p+1,p+m+1);Point ret(0,0);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int x=p[i].x,y=p[i].y;
		if(Find(x)!=Find(y)){
			ret.x+=a[p[i].id];
			ret.y+=b[p[i].id];
			fa[Find(y)]=Find(x);
		}
	}
	return ret;
}

Point Solve(Point l,Point r){
	for(int i=1;i<=m;i++)
		p[i]=Node(u[i],v[i],b[i]*(r.x-l.x)-a[i]*(r.y-l.y),i);
	Point mid=Get_Ans();
	if(mid==l||mid==r)return l.x*l.y<r.x*r.y?l:r;
	l=Solve(l,mid);r=Solve(mid,r);
	return l.x*l.y<r.x*r.y?l:r;	
}

int main(){
	freopen("timeismoney.in","r",stdin);
	freopen("timeismoney.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u[i],&v[i]);u[i]+=1;v[i]+=1;
		scanf("%d%d",&a[i],&b[i]);
	}
	
	for(int i=1;i<=m;i++)p[i]=Node(u[i],v[i],a[i],i);lo=Get_Ans();
	for(int i=1;i<=m;i++)p[i]=Node(u[i],v[i],b[i],i);hi=Get_Ans();	
	Point ans=Solve(lo,hi);
	printf("%d %d\n",ans.x,ans.y);	
	return 0;
}