UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215255#2437. 随机游走KXG1002130ms48676kbC++111.9kb2024-11-27 20:31:372024-11-27 23:38:29

answer

#include <cstdio>
#include <vector>
using namespace std;
vector<pair<int, long long> > G[500010];
int col[500010], vis[500010], flag;
int n, m, s, u, v, fa[500010], deg[500010];
long long w;
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    fa[find(x)] = find(y);
}
void dfs(int u) {
    vis[u] = true;
    for (pair<int, long long> e : G[u]) {
        int v = e.first;
        if (!vis[v]) {
            col[v] = col[u] ^ 1;
            dfs(v);
        } else if (col[v] == col[u]) {
            flag = true;
        }
        if (flag) return;
    }
}
long double a;
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%lld", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
        merge(u, v);
    }
    dfs(s);
    if (flag) {
        long long sum = 0;
        for (int i = 1; i <= n; i++) {
            if (find(i) == find(s)) {
                for (pair<int, long long> e : G[i]) {
                    if (find(e.first) == find(s)) {
                        sum += e.second;
                        deg[i] += e.second;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            printf("%.18Lf ", deg[i] / (long double)sum);
        }
    } else {
        long long sum = 0;
        for (int i = 1; i <= n; i++) {
            if (find(i) == find(s) && col[i] == col[s]) {
                for (pair<int, long long> e : G[i]) {
                    if (find(e.first) == find(s)) {
                        sum += e.second;
                        deg[i] += e.second;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            printf("%.18Lf ", deg[i] / (long double)sum);
        }
    }
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 12844kb

input:

2 2 1
1 2 552418
2 1 687983

output:

1.000000000000000000 0.000000000000000000 

result:

ok 2 numbers

Test #2:

score: 10
Accepted
time: 0ms
memory: 12848kb

input:

15 20 6
1 4 828
2 4 337
3 14 927
5 8 390
6 3 646
7 4 48
9 5 349
10 4 485
11 4 620
12 4 276
13 4 714
...

output:

0.087903385468224114 0.033359730746386854 0.000000000000000000 0.000000000000000000 0.00000000000000...

result:

ok 15 numbers

Test #3:

score: 10
Accepted
time: 3ms
memory: 12844kb

input:

20 20 14
1 19 1746
2 17 3922
3 7 5216
4 18 5768
5 19 4
6 16 5240
8 14 7366
9 8 4420
10 20 8517
11 9 ...

output:

0.131755652239519151 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.00005029801574...

result:

ok 20 numbers

Test #4:

score: 10
Accepted
time: 0ms
memory: 12848kb

input:

60 100 40
1 43 752739
2 1 861767
3 21 651385
4 28 364
5 58 949
6 15 267
7 57 247988
8 50 820601
9 14...

output:

0.026720817566261423 0.028019681145450742 0.010793415829654718 0.000016533909907238 0.00988630164736...

result:

ok 60 numbers

Test #5:

score: 10
Accepted
time: 4ms
memory: 12856kb

input:

98 100 53
1 27 986351
2 56 454750
3 36 141367
4 56 344982
5 70 727802
6 24 509565
7 55 776053
8 59 3...

output:

0.000000000000000000 0.008700000323320518 0.000000000000000000 0.006599985731808156 0.01392386505841...

result:

ok 98 numbers

Test #6:

score: 10
Accepted
time: 0ms
memory: 12980kb

input:

817 1926 733
1 629 1
2 215 1
3 248 1
4 130 1
5 469 1
6 682 1
7 776 1
8 110 1
9 415 1
10 321 1
11 303...

output:

0.001038421599169263 0.001557632398753894 0.001038421599169263 0.001817237798546210 0.00233644859813...

result:

ok 817 numbers

Test #7:

score: 10
Accepted
time: 318ms
memory: 33680kb

input:

166666 300000 119635
1 91644 655718
2 54315 300393
3 112333 880100
4 3430 427450
5 127315 74466
6 95...

output:

0.000011219770187623 0.000002002828888911 0.000012710845702227 0.000002849963909163 0.00000526383566...

result:

ok 166666 numbers

Test #8:

score: 10
Accepted
time: 607ms
memory: 46760kb

input:

400000 500000 363488
1 254054 843859
2 169299 701504
3 174552 479095
4 70702 852271
5 301016 4
6 830...

output:

0.000003125789179748 0.000004491298206931 0.000004679186537985 0.000002361895274128 0.00000000001662...

result:

ok 400000 numbers

Test #9:

score: 10
Accepted
time: 549ms
memory: 43460kb

input:

500000 500000 342024
1 367282 471300
2 346217 948546
3 230072 336639
4 458846 88399
5 20450 217996
6...

output:

0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.00000000000000...

result:

ok 500000 numbers

Test #10:

score: 10
Accepted
time: 649ms
memory: 48676kb

input:

466666 500000 456939
1 304818 887447
2 55736 302299
3 283098 150863
4 424825 796422
5 99211 331398
6...

output:

0.000005283509451936 0.000004051838076543 0.000000526536001994 0.000003490082354328 0.00000477969147...

result:

ok 466666 numbers