请问为什么炸成了60
查看原帖
请问为什么炸成了60
336641
Ankaa楼主2020/12/8 22:26
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long LL;

int read() {
	int d = 0, f = 1; char c = getchar(); while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
	while(isdigit(c)) {d = d * 10 + c - '0'; c = getchar();} return d * f;
}

const int maxn = 200010;

int n, m, d[maxn], in[maxn], out[maxn];

struct edge {
	int nxt, to;
}e[maxn * 6];

int tot, head[maxn];

void addedge(int u, int v) {
	e[++tot].nxt = head[u];
	e[tot].to = v;
	head[u] = tot;
}

LL gcd(LL x, LL y) {
	if(y == 0) return x;
	return gcd(y, x % y);
}

struct fenshu {
	LL fz, fm;
}water[maxn];

fenshu div(fenshu a, LL b) {
	fenshu ans;
	ans.fz = a.fz;
	ans.fm = a.fm * b;
	LL g = gcd(ans.fz, ans.fm);
	ans.fz /= g;
	ans.fm /= g;
	return ans;
}

fenshu add(fenshu a, fenshu b) {
	if(a.fz == 0 && a.fm == 0) return b;
	if(b.fz == 0 && b.fm == 0) return a;
	fenshu ans;
	ans.fm = a.fm * b.fm;
	ans.fz = a.fm * b.fz + b.fm * a.fz;
	LL g = gcd(ans.fz, ans.fm);
	ans.fm /= g;
	ans.fz /= g;
	return ans;
}

void topSort() {
	queue<int> q;
	for(int i = 1; i <= n; i++) {
		if(in[i] == 0) {
			q.push(i);
			water[i] = (fenshu){1, 1};
		}
	}
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		fenshu num = div(water[u], out[u]);
		//printf("num=%lld/%lld\n", num.fz, num.fm);
		for(int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			water[v] = add(water[v], num);
			in[v]--;
			if(in[v] == 0) {
				q.push(v);
			}
		}
	}
}

int main() {
//	freopen("water.in", "r", stdin);
//	freopen("water.out", "w", stdout);
	n = read(), m = read();
	for(int i = 1; i <= n; i++) {
		d[i] = read();
		for(int j = 1; j <= d[i]; j++) {
			int t = read();
			addedge(i, t);
			out[i]++;
			in[t]++;
		}
	}
	
	topSort();
	
	for(int i = 1; i <= n; i++) {
		if(out[i] == 0) {
			printf("%lld %lld\n", water[i].fz, water[i].fm);
		}
	}
	return 0;
}
2020/12/8 22:26
加载中...