Be careful. It will play a circle when your Eps<=1e-10. Because Cpp's double is unable to stop the Binary Search. Sorry for my poor Eng I try to find alghoritm for this program, and can't find it. I read in other post next scheme w(x)=a-b*x is weight of every edge Z(x)=0 - solution. how understand w(x) ? Can I solve this problem without Z(x)=0 ? Я также хотел бы почитать про данную идею решения. На форуме есть ссылка на статью, но она на недоступном для меня английском языке. Насколько я понял с помощью Google переводчика, на форуме обсуждается следующее:каждому ребру присваивается вес w(x)=a-x*b, a-себестоимость, b-расстояние. Рассматривается целевая функция Z(x)=Sum(a,x,E)-x*Sum(b,x,E), где E-рёбра минимального остова с весовой ф-ей w(x), x-параметр, Sum(a,x,E) = Sum(a) в E, Sum(b,x,E) = Sum(b) в E (или Z(x)=Sum(w(x) в E)). Уверяется, что решение задачи 1447 достигается только в т.х : Z(x)=0. Док-во (моё): Сразу скажем, что ai,bi>0; 1)Необх.: пусть х - решение => Sum(a,E)/Sum(b,E)=x -> min => Sum(a,E)-x*Sum(b,E)=0, т.е. Z(x)=Sum(a,x,E)-Sum(b,x,E)=0 2)Дост.: пусть Z(x)=0, но y<x - решение, Ey - соответствующий набор рёбер для y; Z(y)=0 (из 1)); в силу минимального остова 0=Z(x)=Sum(a,x,E)-x*Sum(b,x,E)<=Sum(a,x,Ey)-x*Sum(b,x,Ey)=> Sum(a,Ey)>=x*Sum(b,Ey)>y*Sum(b,Ey) => Sum(a,Ey)-y*Sum(b,Ey)=Z(y)>0 - противоречие. Свойства: Пусть Z(x)=0. Тогда: 1)y<x <=> Z(y)>0 2)y>x <=> Z(y)<0 (Доказывается просто) Edited by author 22.11.2017 22:34 用 scanf ,不要用cin 用 Prim ,不要用Kruskal use scanf instead of cin use Prim instead of Kruskal no ,you can use Dinkelbach I use bs + MST(Prim), please help me!!! Here is my code: #include <iostream> #include <iomanip> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #define MAXN 1005 #define MAXE 500005 #define oo 1e100 #define EPS 1e-9 #define nabs(x) ((x) < 0? -(x) : (x)) using namespace std; struct edge { int to, l, c, back; edge() { } edge(int _to, int _l, int _c, int _back) { to = _to; l = _l; c = _c; back = _back; } } E[MAXE + MAXE]; int n, m, ce; int ptr[MAXN]; long double d[MAXN]; bool mark[MAXN]; void add_edge(int a, int b, int l, int c) { E[ce] = edge(b, l, c, ptr[a]); ptr[a] = ce++; E[ce] = edge(a, l, c, ptr[b]); ptr[b] = ce++; } long double Prim(long double x) { for (int i = 1; i < n + 1; i++) d[i] = oo; d[1] = 0; long double res = 0, _min, val; int v, w; memset(mark, 0, sizeof(mark)); for (int pass = 0; pass < n; pass++) { _min = oo; for (int i = 1; i < n + 1; i++) if (!mark[i] && d[i] < _min) { v = i; _min = d[i]; } mark[v] = true; res += _min; for (int i = ptr[v]; i != -1; i = E[i].back) { w = E[i].to; val = E[i].c - x * E[i].l; d[w] = min(d[w], val); } } return res; } int main() { int a, b, l, c; memset(ptr, -1, sizeof(ptr)); scanf("%d%d", &n, &m); while (m--) { scanf("%d%d%d%d", &a, &b, &l, &c); add_edge(a, b, l, c); } if(n == 1){ cout << "0" << endl; return 0; } long double lo = 0, hi = 1e15, mit, fmit, flo; for (; nabs(hi - lo) > EPS;) { mit = (lo + hi) / 2; fmit = Prim(mit); flo = Prim(lo); if (flo * fmit < 0) hi = mit; else lo = mit; } cout << setprecision(8) << lo << endl; } Binary search over A such that Z(A) = 0 gives TL 30. Is it necessary to use sparsification or other sophisticated methods? When m = 500000, n = 1000 reading of input data (~10mb) takes about 2.5 sec. I'm wonder how could people to solve it in 0.6 sec.. Just ideas or links what should i read to solve it. or at least your solution complexity.. Edited by author 20.04.2007 02:42 hm.. I think your solution correct can you explain how to use bs I can send to you c++ prog wich read 10Mb ~ 0.6-0.7 sec Assign with each edge weight function w(x) = a - bx, where a = numerator, b - denominator. Let z(x) weight of minimal spanning tree at point x. If we find such x, that z(x) = 0 (such value always exists), x will be answer. Thank you but why it works, is it standart method? I think only optimisation is needed You will call SpanTree O(n^2) not more then 50 times It takes less then 2 sec You can speed up input several times If write like this scanf("%d%d%d%d\n",&a,&b,&c,&d); on 10Mb it will work ~3 sec TLE 34 :( I used mix of binary search and Mediggo's approach. >>You will call SpanTree O(n^2) not more then 50 times And how to solve MST in O(n^2)? Edited by author 28.04.2007 16:05 I used just plain binary search and computed the MST with Prim's algorithm. No complicated data structures or Megiddo's aproach are needed here. Just some small optimizations on the code. Thanks a lot! I finally solved it in 0.375. But can't optimize to your 0.359 :) Edited by author 04.09.2008 20:32 I constantly got with binary search TL6. Then I replaced binary search with iterative approach. I.e. build MST tree for x=1e+6, then build MST with whatever ratio previous tree had. Proceed until improvement is >1e-8. Now AC :) Binary search works VERY fast if you combine it with disjoint sets It does not matter here because edge-sorting step consumes O(N^2*log(N)) time. Problem statement claims N>=1. I think it should be N>=2. I don't find my bug. More test please... |
|