1 条题解
-
6
#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
- 标签
- 递交数
- 129
- 已通过
- 51
- 上传者