play with precision

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 ?

用 scanf ,不要用cin
用 Prim  ,不要用Kruskal

use scanf instead of cin
use Prim instead of Kruskal

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

Problem statement claims N>=1. I think it should be N>=2.

use read, no readln.