bzoj 2395 [Balkan 2011]Timeismoney—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2395

如果把 \( \sum t \) 作为 x 坐标，\( \sum c \) 作为 y 坐标，则每棵生成树都是二维平面上的一个点。

答案是二维平面上的一个下凸壳。先求出只考虑 t 的最小生成树和只考虑 c 的最小生成树，它们就是凸壳的两端。

已知两端，考虑递归下去，则要找到距离这两端构成的直线最远的点。

这就是点到直线的距离，等价于三个点组成的三角形面积最小；考虑叉积公式，得出面积关于要找的点的 x , y 坐标的式子，形如 A*x + B*y ；

给边权乘上系数，就能求最小生成树得到该点；如果面积是负的，就求最小生成树，否则求最大生成树。

判断是否不用再往下递归，本来写的是找到的那个点就是两端点之一，结果T了；写成找到的那个点在两端点的连线上就可以了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=,M=1e4+;

int n,m,fa[N],dep[N];

struct Ed{int t,c,w,x,y;}ed[M];

struct Node{

  int t,c;ll w;

  Node(){t=c=w=;}

  bool operator== (const Node &b)const

  {return t==b.t&&c==b.c;}

}ans;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

void frh(Node p){if(p.w<ans.w||(p.w==ans.w&&p.c<ans.c))ans=p;}

bool cmp(Ed u,Ed v){return u.w<v.w;}

int fnd(int a){return fa[a]==a?a:fa[a]=fnd(fa[a]);}

ll Cross(int x1,int y1,int x2,int y2)

{return (ll)x1*y2-(ll)x2*y1;}

Node calc(int t0,int t1)

{

  for(int i=;i<=m;i++)ed[i].w=(ll)t0*ed[i].t+(ll)t1*ed[i].c;

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

  memset(dep,,sizeof dep);

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

  Node ret;

  for(int i=,u,v,cnt=;i<=m;i++)

    {

      if((u=fnd(ed[i].x))==(v=fnd(ed[i].y)))continue;

      if(dep[u]>dep[v])swap(u,v);

      fa[u]=v;if(dep[u]==dep[v])dep[v]++;

      ret.t+=ed[i].t;ret.c+=ed[i].c;

      cnt++;if(cnt==n-)break;

    }

  ret.w=(ll)ret.t*ret.c;

  return ret;

}

void solve(Node p0,Node p1)

{

  int st=p1.c-p0.c,sc=p0.t-p1.t;

  Node res=calc(st,sc);frh(res);

  //  if(res==p0||res==p1)return;

  if(Cross(p1.t-res.t,p1.c-res.c,p0.t-res.t,p0.c-res.c)>=)return;

  solve(p0,res); solve(res,p1);

}

int main()

{

  n=rdn();m=rdn();

  for(int i=;i<=m;i++)

    ed[i].x=rdn()+,ed[i].y=rdn()+,ed[i].t=rdn(),ed[i].c=rdn();

  ans.t=ans.c=1e9;ans.w=1e18;

  Node p0=calc(,),p1=calc(,);

  frh(p0);frh(p1);

  solve(p0,p1);

  printf("%d %d\n",ans.t,ans.c);

  return ;

}

巴特西

bzoj 2395 [Balkan 2011]Timeismoney——最小乘积生成树

最新文章

热门文章