bzoj2395
每条边有两个权值，c[i],t[i],求一棵生成树使sigma(c[i])*sigma(t[i])最小
ž设Sigma（a）*sigma(b)=k
ž则sigma（b）=k/sigma(a),是个反比例函数，求出y坐标最小的和x坐标最小的，则将两个点连线，之上的点肯定不优，接着用此线去切(以此斜率类似最优比率生成树去判定,此处最好不用实数，很慢很慢)，切点是最优解的候选解，再递归去连线（三角形内部点肯定不优）
ž直到新的点在两点直线上。
最后两个点卡常数啊，我调了很久，double不能用，要改为B*C[I]+A*T[I]。原理大约是用凸壳，但是为什么求出斜率后再求mst就不知道了。
次小乘积生成树
žWc众神犇也没yy出来。
ž大概有两种思路。
ž第一种在次小凸壳（每次选次小点）找最小点并在最小凸壳找次小点（正确性完全木有证明）
ž第二种不记得了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
struct line
{
int i;int w;
}a[10050],p,q;
const int maxn=210;
int fa[maxn],n,m,l[10050],r[10050];
int c[10050],t[10050],anc,ant,ans;
double pd;
int find(int x) {if (fa[x]!=x) fa[x]=find(fa[x]);return fa[x];}
void updata(int cc,int tt) {if (cc*tt<ans) ans=cc*tt,anc=cc,ant=tt;}
int cmp1(const void *i,const void *j)
{
p=*(line *)i,q=*(line *)j;
pd=p.w-q.w;
if (pd>0) return 1;else return -1;
}
void kruskal(int &cc,int &tt)
{
int i,j,ll,rr;
qsort(a+1,m,sizeof(a[1]),cmp1);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=m;i++)
{
ll=find(fa[l[a[i].i]]),rr=find(fa[r[a[i].i]]);
if (ll!=rr) fa[rr]=ll,cc+=c[a[i].i],tt+=t[a[i].i];
}
}
int cmp(int px,int py,int qx,int qy) {return (px*qy-py*qx);}
void dfs(int ac,int at,int bc,int bt)
{
int cc=0,tt=0;
int A=bc-ac,B=at-bt;
for (int i=1;i<=m;i++) a[i].w=B*c[a[i].i]+A*t[a[i].i];
kruskal(cc,tt);
if (cmp(ac-bc,at-bt,cc-bc,tt-bt)<=0) {updata(ac,at),updata(bc,bt);return ;}
dfs(ac,at,cc,tt),dfs(cc,tt,bc,bt);
}
void init()
{
int i,x,y;
int ac=0,at=0,bc=0,bt=0;
scanf("%d%d\n",&n,&m);
for (i=1;i<=m;i++) scanf("%d%d%d%d\n",&x,&y,&c[i],&t[i]),x++,y++,l[i]=x,r[i]=y;
ans=1073741819,anc=0,ant=0;
for (i=1;i<=m;i++) a[i].w=c[i],a[i].i=i;
kruskal(ac,at);updata(ac,at);
for (i=1;i<=m;i++) a[i].w=t[a[i].i];
kruskal(bc,bt);updata(bc,bt);
if ((ac!=bc)||(at!=bt)) dfs(ac,at,bc,bt);
printf("%d %d\n",anc,ant);
}
int main()
{
freopen("timeismoney.in","r",stdin);
freopen("timeismoney.out","w",stdout);
init();
return 0;
}