ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#215255 | #2437. 随机游走 | KXG | 100 | 2130ms | 48676kb | C++11 | 1.9kb | 2024-11-27 20:31:37 | 2024-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