1 条题解

  • 6
    @ 2023-8-28 23:23:32
    #include<bits/stdc++.h>
    #define fo(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
    #define INF 0x7fffffff
    #define mod 1000000007
    #define eps 1e-6
    
    using namespace std;
    typedef unsigned long long ull;
    typedef long long ll;
    
    const int N = 1000010;
    const int M = 1000010;
    ll n,m;
    struct GraphEdge{
        ll to,next;
    }edge[M];
    ll head[N] = {0},num = 0;
    
    struct GraphNode{
        ll outdegree;
        ll indegree;
    }node[N];
    
    void add(ll u,ll v){
        edge[++num].to = v;
        edge[num].next = head[u];
        head[u] = num;
        node[u].outdegree++;
        node[v].indegree++;
    }
    
    bool vis[N] = {0};
    ll node_cnt = 0;
    
    ll tp_s[N] = {0};
    ll top = 0;
    
    void solve(){
        queue<ll> q;
        for(ll i = 1;i <= n;i++){
            if(node[i].indegree == 0)
                q.push(i);
        }
        while(!q.empty()){
            ll p = q.front(); q.pop();
            vis[p] = true;
            tp_s[++top] = p;
            for(ll i = head[p];i;i = edge[i].next){
                ll to = edge[i].to;
                if(!vis[to]){
                    node[to].indegree--;
                    if(node[to].indegree == 0){
                        q.push(to);
                    }
                }
            }
        }
    }
    
    inline void bwr(__int128 x) {
        if(x < 0) { putchar('-'); x = -x; }
        if(x > 9) bwr(x / 10); putchar(x % 10 + '0');
    }
    
    __int128 Gcd_(__int128 a,__int128 b){
        if(a % b == 0)return b;
        return Gcd_(b,a % b);
    }
    
    __int128 Lcm_(const __int128 &a,const __int128 &b){ return a * b / Gcd_(a,b); }
    
    struct Frac{
        __int128 up,down;
        Frac(){}
        Frac(__int128 up_,__int128 down_) : up(up_) , down(down_) {}
    }flow_ans[N];
    
    Frac operator + (const Frac &x,const Frac &y){
        __int128 tlcm__ = Lcm_(x.down,y.down);
        return Frac(tlcm__ / x.down * x.up + tlcm__ / y.down * y.up,tlcm__);
    }
    
    Frac operator * (const Frac &x,const Frac &y){
        return Frac(x.up * y.up,x.down * y.down);
    }
    
    Frac ts_F(const Frac &x){
        __int128 tgcd__ = Gcd_(x.up,x.down);
        return Frac(x.up / tgcd__,x.down / tgcd__);
    }
    
    int main() {
        scanf("%lld%lld",&n,&m);
        ll u,d;
        for(ll i = 1;i <= n;i++){
            if(i <= m)flow_ans[i] = Frac(1,1);
            else flow_ans[i] = Frac(0,1);
            scanf("%lld",&d);
            for(ll j = 1;j <= d;j++){
                scanf("%lld",&u);
                add(i,u);
            }
        }
        solve();
        for(ll i = 1;i <= n;i++){
            if(node[tp_s[i]].outdegree == 0){
                continue;
            }
            // printf("%lld ",tp_s[i]);
            for(ll j = head[tp_s[i]];j;j = edge[j].next){
                ll to = edge[j].to;
                // printf("%lld ",to);
                flow_ans[to] = flow_ans[tp_s[i]] * Frac(1,node[tp_s[i]].outdegree) + flow_ans[to];
                flow_ans[to] = ts_F(flow_ans[to]);
            }
            // printf("\n");
        }
        for(ll i = 1;i <= n;i++){
            if(node[i].outdegree == 0){
                bwr(flow_ans[i].up); cout << " "; bwr(flow_ans[i].down);
                cout << endl;
            }
        }
        return 0;
    }
    
    
    
    • 1

    信息

    ID
    2015
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    128
    已通过
    50
    上传者