【最小積生成ツリー】bzoj 2395

bzoj 2395以前キゴの話を聞いたとき、あまり分からなかったので、書きにくいと思っていましたが、実は書きにくいのではなく、少し調子が悪いだけです.数形結合の考え方を用いて,各生成木が座標系で点(sigma(a),sigma(b))に対応すると,最小積生成木は必ずあるk最小の逆比例関数xy=kにある.まずsigma(a)最小の点を求め,sigma(b)の最小の点は,速包思想を用いて,この2点が連なる直線から最も遠い(原点に近い方へ)点を探す.(生成樹)c,三角形が得られ,三角形内部の点はcに及ばず排除でき,その後a-->c,c->bを再帰的に処理する場合.複雑度......適応シンプソンのように複雑度は確定しにくいが,速度は信じられる.脳がkruscalを抽出したためである.(図が便利でprimがブスになった)、結果が遅くてぼろぼろになった=.=、ちょっとした最適化を加えてやっと過ぎたが、やはり最下位だった.primを直したくない.primも書きやすいが.今回は災いのおかげでやっと早く並ぶことができた=.=!、お祝いしよう.

# include <cstdlib>
# include <cstdio>
# include <cmath>

using namespace std;

const int maxV= 10000+5;

struct point
{
  int a,b,x,y; long long c;
  void read()
  {
    scanf("%d%d%d%d",&x,&y,&a,&b);
    x++,y++;
  }
}ans,edge[maxV];

int ufs[300];
int n,m;
int find(int x) {return ufs[x]==x? x:x= find(ufs[x]);};

int cmp(const void *i, const void *j)
{
  point p=*(point *)i, q=*(point *)j;
  if (p.c>q.c) return 1; else return -1;
}

inline point kruscal()
{
  int i,fx,fy; point p; p.a=p.b=0; int k = 0;
  for (i = 1; i <= n; i++) ufs[i] = i;
  for (i = 1; i <= m; i++)
  {
    fx = find(edge[i].x), fy = find(edge[i].y);
    if (fx!= fy) p.a+= edge[i].a, p.b+= edge[i].b, ufs[fx]=fy, k++;
    if (k == n-1) break;
  }
  if (1LL*ans.a*ans.b>1LL*p.a*p.b) ans = p;
  return p;
}

inline long long cross(long long x1, long long y1, long long x2, long long y2)
{
	return x1*y2-x2*y1;
}

void work(point blim, point alim)
{
  int kb = alim.b-blim.b, ka= alim.a-blim.a, i; point p;
  for (i = 1; i <= m; i++) edge[i].c= 1LL*edge[i].a*kb-1LL*edge[i].b*ka;
  qsort(edge+1, m, sizeof(edge[1]), cmp);
  p = kruscal(); 
  if (cross(1LL*alim.a-blim.a, 1LL*alim.b-blim.b, 1LL*p.a-blim.a, 1LL*p.b-blim.b)  <=0) return;
      work(p, alim); 
      work(blim, p);
}
 
int main()
{
  int i; point alim, blim;
  freopen("timeismoney.in", "r", stdin);
  freopen("timeismoney.out", "w", stdout);
  scanf("%d%d", &n, &m); ans.a=ans.b=1073740819;
  for (i = 1; i <= m; i++)
    edge[i].read();
  for (i = 1; i <= m; i++) edge[i].c=edge[i].a;
  qsort(edge+1, m, sizeof(edge[1]),cmp);
  alim = kruscal();
  for (i = 1; i <= m; i++) edge[i].c=edge[i].b;
  qsort(edge+1, m, sizeof(edge[1]),cmp); 
  blim = kruscal();
  work(blim, alim);
  printf("%d %d",ans.a, ans.b); 
  return 0;
}