why WA on test 4, please give me some testcases.
Posted by
Ycid 30 Sep 2012 10:04
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;
}