ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1447. Portkey Network

why WA on test 4, please give me some testcases.
Posted by Ycid 30 Sep 2012 10:04

#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);
}

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;

}