bzoj2395: [Balkan 2011]Timeismoney

Description

有n个城市(编号从0..n-1)，m条公路(双向的)，从中选择n-1条边，使得任意的两个城市能够连通，一条边需要的c的费用和t的时间，定义一个方案的权值v=n-1条边的费用和*n-1条边的时间和，你的任务是求一个方案使得v最小

Input

第一行两个整数n,m,接下来每行四个整数a,b,c,t,表示有一条公路从城市a到城市b需要t时间和费用c

Output

【output】timeismoney.out

仅一行两个整数sumc，sumt,（sumc表示使得v最小时的费用和，sumc表示最小的时间和）如果存在多个解使得sumc*sumt相等，输出sumc最小的

Sample Input

5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92

Sample Output

279 501

HINT

【数据规模】

1<=N<=200

1<=m<=10000

0<=a,b<=n-1

0<=t,c<=255

有5%的数据m=n-1

有40%的数据有t=c

对于100%的数据如上所述

题解：

终于知道什么是最小乘积生成树了

其实hnoi的画框 http://www.cnblogs.com/chenyushuo/p/5066481.html 也用了它的思想

code：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define maxn 205

 #define maxm 10005

 using namespace std;

 char ch;

 bool ok;

 void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 int n,m;

 int fa[maxn];

 int u[maxm],v[maxm],val[maxm],tim[maxm],cost[maxm];

 struct Point{

     int x,y;

     bool operator==(Point b){return x==b.x&&y==b.y;}

 }st,ed,ans;

 struct Edge{

     int u,v,val,id;

 }edge[maxm];

 bool cmp(Edge a,Edge b){return a.val<b.val;}

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

 Point kruskal(){

     for (int i=;i<=m;i++) edge[i]=(Edge){u[i],v[i],val[i],i};

     sort(edge+,edge+m+,cmp);

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

     int cnt=;

     Point ans; ans=(Point){,};

     for (int i=;i<=m&&cnt<n;i++)

         if (find(edge[i].u)!=find(edge[i].v)){

             fa[find(edge[i].u)]=find(edge[i].v);

             cnt++,ans.x+=tim[edge[i].id],ans.y+=cost[edge[i].id];

         }

     return ans;

 }

 Point calc(Point a,Point b){return a.x*a.y<b.x*b.y?a:b;}

 Point solve(Point st,Point ed){

     Point mid;

     for (int i=;i<=m;i++) val[i]=tim[i]*(st.y-ed.y)-cost[i]*(st.x-ed.x);

     mid=kruskal();

     if (st==mid||ed==mid) return calc(st,ed);

     return calc(solve(st,mid),solve(mid,ed));

 }

 int main(){

     read(n),read(m);

     for (int i=;i<=m;i++) read(u[i]),read(v[i]),u[i]++,v[i]++,read(tim[i]),read(cost[i]);

     for (int i=;i<=m;i++) val[i]=tim[i];

     st=kruskal();

     for (int i=;i<=m;i++) val[i]=cost[i];

     ed=kruskal();

     ans=solve(st,ed);

     printf("%d %d\n",ans.x,ans.y);

     return ;

 }

巴特西