M_sea

洛谷4581 [BJOI2014]想法
Luogu分析乱搞?分析题面,发现意思大概是给你一个$\texttt{DAG}$,问每个点能从多少个入度为$0$的...
扫描右侧二维码阅读全文
24
2019/01

洛谷4581 [BJOI2014]想法

Luogu

分析

乱搞?

分析题面,发现意思大概是给你一个$\texttt{DAG}$,问每个点能从多少个入度为$0$的点到达。

一眼不会做,然后发现这个$\texttt{SPJ}$比遥远的行星误差还大。

于是可以乱搞,给所有入度为$0$的点$\texttt{rand}$一个权值,然后将每个点的权值设为所有能到达这个点的点权的最小值。

经过一番推导后可以发现,这个权值的期望是$\frac{\texttt{RAND_MAX}}{k}$($k$是能到达这个点的入度为$0$的点的个数)。

大概随机个$100$次就行了,最后取个平均就是答案。

时间复杂度$O(Tn)$,$T$是随机的次数。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define min(a,b) (((a)<(b))?(a):(b))
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int T=100;
const int N=1000000+10;

int x[N],y[N],w[N];
double ans[N];

int main() {
    srand(19260817);
    int n=read(),m=read();
    for (re int i=m+1;i<=n;++i) x[i]=read(),y[i]=read();
    for (re int t=1;t<=T;++t) {
        for (re int i=1;i<=m;++i) w[i]=rand();
        for (re int i=m+1;i<=n;++i) {
            w[i]=min(w[x[i]],w[y[i]]);
            ans[i]+=w[i];
        }
    }
    for (re int i=m+1;i<=n;++i)
        printf("%d\n",(int)(RAND_MAX/ans[i]*T-0.5));
    return 0;
}
最后修改:2019 年 05 月 26 日 07 : 52 PM

1 条评论

  1. smy

    这都会%%%%%%

发表评论