UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215275#2437. 随机游走N100999ms53940kbC++112.7kb2024-11-27 22:26:382024-11-27 23:40:08

answer

//
//  na 2437.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/27.
//

#include <stdio.h>
#include <iostream>
#include <time.h>
#include <random>
using namespace std;
const int maxn = 5e5 + 5;
int n, m, s, ul[maxn], vl[maxn], wl[maxn];
bool vis[maxn], col[maxn];
double wsum[maxn], plist1[maxn], plist2[maxn];
double *lp = plist1, *np = plist2;
struct Edge{
    int i, w; Edge *nxt;
    Edge(int i, int w, Edge *nxt): i(i), w(w), nxt(nxt) {}
};
Edge *head[maxn];
inline void edge(int st, int en, int w){ head[st] = new Edge(en, w, head[st]); }
#define trav(x) for(Edge *e = head[x]; e != nullptr; e = e->nxt)
template<typename T> inline void rd(T &v){
    v = 0; char r = getchar();
    while(r - 48 >= 10u)
        r = getchar();
    while(r - 48 < 10u){
        v = (v << 3) + (v << 1) + (r ^ 48);
        r = getchar();
    }
}
inline void sim(){
    swap(lp, np);
    for(int i = 1; i <= n; ++i)
        np[i] = 0;
    for(int i = 1; i <= n; ++i)
        trav(i)
            np[e->i] += lp[i] * (e->w / wsum[i]);
}
bool bi = true;
void dfs(int idx, bool nc){
    if(vis[idx]){
        if(col[idx] != nc)
            bi = false;
        return;
    }
    vis[idx] = true;
    col[idx] = nc;
    trav(idx) dfs(e->i, !nc);
}
inline void norm(){
    double ps = 0;
    for(int i = 1; i <= n; ++i)
        ps += np[i];
    for(int i = 1; i <= n; ++i)
        np[i] /= ps;
}
int main(){
    clock_t st = clock();
    cin.tie(0)->sync_with_stdio(false);
    rd(n); rd(m); rd(s);
    for(int i = 0; i < m; ++i){
        rd(ul[i]); rd(vl[i]); rd(wl[i]);
        edge(ul[i], vl[i], wl[i]);
        edge(vl[i], ul[i], wl[i]);
        wsum[ul[i]] += wl[i];
        wsum[vl[i]] += wl[i];
    }
    dfs(s, true);
//    np[s] = 1;
//    random_device rd;
//    mt19937 rnd(rd());
//    uniform_real_distribution<> dis(0.0, 1.0);
//    for(int i = 1; i <= n; ++i)
//        if(vis[i])
//            np[i] = dis(rnd);
    for(int i = 1; i <= n; ++i)
        if(vis[i])
            np[i] = wsum[i];
    norm();
//    for(int i = 1; i <= n; ++i)
//        cerr << np[i] << ' ';
//    cerr << endl;
//    bool f = false;
//    while(double(clock() - st) / CLOCKS_PER_SEC < 0.7 || f){
//        sim();
//        f = !f;
//    }
//    cerr << "BIPART? " << bi << endl;
    if(bi){
        double ps = 0;
        for(int i = 1; i <= n; ++i)
            if(col[i])
                ps += np[i];
        for(int i = 1; i <= n; ++i)
            if(col[i])
                printf("%.10f ", np[i] / ps);
            else
                printf("0 ");
    }else{
        for(int i = 1; i <= n; ++i)
            printf("%.10f ", np[i]);
    }
    printf("\n");
    return 0;
}

Details

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

Test #1:

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

input:

2 2 1
1 2 552418
2 1 687983

output:

1.0000000000 0 

result:

ok 2 numbers

Test #2:

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

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.0879033855 0.0333597307 0 0 0 0.0639477331 0.0929518907 0.0386062166 0.0345476143 0.0480102950 0.1...

result:

ok 15 numbers

Test #3:

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

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.1317556522 0 0 0 0.0000502980 0.1327993361 0.1483665719 0 0.1738299424 0 0 0.0729446973 0.02474662...

result:

ok 20 numbers

Test #4:

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

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.0267208176 0.0280196811 0.0107934158 0.0000165339 0.0098863016 0.0000044190 0.0420015432 0.0135919...

result:

ok 60 numbers

Test #5:

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

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 0.0087000003 0 0.0065999857 0.0139238651 0.0097486876 0.0148469738 0.0155966565 0.0081356243 0.015...

result:

ok 98 numbers

Test #6:

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

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.0010384216 0.0015576324 0.0010384216 0.0018172378 0.0023364486 0.0012980270 0.0007788162 0.0015576...

result:

ok 817 numbers

Test #7:

score: 10
Accepted
time: 148ms
memory: 29872kb

input:

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

output:

0.0000112198 0.0000020028 0.0000127108 0.0000028500 0.0000052638 0.0000034816 0.0000056758 0.0000050...

result:

ok 166666 numbers

Test #8:

score: 10
Accepted
time: 340ms
memory: 53240kb

input:

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

output:

0.0000031258 0.0000044913 0.0000046792 0.0000023619 0.0000000000 0.0000005829 0.0000031231 0.0000048...

result:

ok 400000 numbers

Test #9:

score: 10
Accepted
time: 147ms
memory: 50196kb

input:

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

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 500000 numbers

Test #10:

score: 10
Accepted
time: 364ms
memory: 53940kb

input:

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

output:

0.0000052835 0.0000040518 0.0000005265 0.0000034901 0.0000047797 0.0000000000 0.0000020424 0.0000000...

result:

ok 466666 numbers