1 条题解
-
0Guest LV 0 MOD
-
0
代码质量不高,但是思路有的。
C++代码,__int128(NOIP新标准)。
#include <bits/stdc++.h> #define int unsigned __int128 //高精度. using namespace std; const int N = 1e5 + 5; void put(int x) { //高精度输出. if(x < 10) {putchar(x + '0'); return;} else {put(x / 10); putchar(x % 10 + '0');} } int read() { //高精度输入. int x = 0; char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return x; } int n, m, dr[N], book[N]; int gcd(int x, int y) { //最大公约数,用以给分数约分. if(y == 0) return x; return gcd(y, x % y); } struct valuex { //分数相关处理. int p, q; void putin(int x, int y) {p = x; q = y;} //赋值. void putout() {put(p); putchar(' '); put(q);} //输出. valuex makenew() { //约分. int px, qx; px = p; qx = q; int tmp = gcd(qx, px); qx /= tmp; px /= tmp; return (valuex){px, qx}; } valuex add(valuex x, valuex y) { //分数相加. int px, qx; qx = x.q * y.q; px = x.p * y.q + y.p * x.q; valuex tmp = (valuex){px, qx}; tmp = tmp.makenew(); return tmp; } valuex doso(valuex a, int x) { //分数乘某个数. q *= x; return makenew(); } valuex getin(){return (valuex){p, q};} //得到值,基本没用. } nox[N]; vector<int> e[N]; //vector存储图. int que[N]; //队列,拓扑部分. signed main() { //主函数. n = read(); m = read(); //读入. for(int i = 1, dt; i <= n; i++) { dt = read(); for(int j = 1, to; j <= dt; j++) { to = read(); e[i].push_back(to); dr[to]++; } } int head = 0, tail = 0; //找起始点. for(int i = 1; i <= n; i++) if(dr[i] == 0) que[++tail] = i; for(int i = head; i <= tail; i++) nox[que[i]].putin(1, 1); while(head < tail) { head++; valuex temp = nox[que[head]].getin(); valuex tmp = temp.doso(temp, e[que[head]].size()); for(int i = 0; i < e[que[head]].size(); i++) { int to = e[que[head]][i]; dr[to]--; if(!dr[to]) que[++tail] = to; if(!book[to]) { nox[to] = tmp; book[to] = 1; } else nox[to] = tmp.add(tmp, nox[to]); } } for(int i = 1; i <= n; i++) //没有通出节点,处理,输出. if(e[i].size() == 0) { nox[i].putout(); printf("\n"); } return 0; }
- 1