30pt WA+TEL求助
查看原帖
30pt WA+TEL求助
148184
Charser茶色楼主2020/12/19 17:01
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define in(a) scanf("%lld",&a);
#define ll long long
using namespace std;
const int N=100005;
ll gcd(ll m,ll n){return m%n==0? n : gcd(n,m%n);}
struct Edge{
	int to,nex;
}edge[N*10];
struct fen{
	ll zi,mu;
	fen(int zi=0,int mu=1){this-> zi = zi;this-> mu = mu;}
	void simp(){
		ll nn=gcd(this->mu,this->zi);
		if(nn>1){this->mu /= nn;this->zi /= nn;}
	}
}point[N],one(1,1);
fen operator + (const fen& A,const fen& B){
	fen A1=A,B1=B;
	if(A1.mu!=B1.mu){
		ll nn=gcd(B1.mu,A1.mu);
	    B1.zi=A1.mu/nn*B1.zi; A1.zi*=B1.mu/nn*A1.zi;
	    B1.mu=A1.mu=A1.mu/nn*B1.mu;
	}
	fen C(A1.zi+B1.zi,B1.mu);
	C.simp();
	return C;
}
fen operator / (const fen& A,const ll& x){
	fen C(A.zi,A.mu*x);
	C.simp();
	return C;
}
ostream& operator << (ostream &out, const fen& p){
	out<<p.zi<<" "<<p.mu<<endl;
	return out;
}
ll n,stsum,edsum[N],tot=0;
ll headlist[N],indo[N],outdo[N];
bool vis[N];
queue<int> tuop;
void adds(int x,int y){
	edge[++tot].nex=headlist[x];
	edge[tot].to=y;
	headlist[x]=tot;
}
int main(){
	freopen("water4.in","r",stdin);
	freopen("water.out","w",stdout);
	in(n);in(stsum);
	for(int i=1;i<=stsum;i++) point[i]=one;
	for(int i=1;i<=n;i++){
	    in(outdo[i]);
		for(int j=1;j<=outdo[i];j++){int y;
		    in(y);
			indo[y]++;
		    adds(i,y);
		}
		if(!outdo[i]){edsum[0]++;edsum[edsum[0]]=i;}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!vis[j]&&!indo[j]){
				vis[j]=true;
			    tuop.push(j);
			    for(int k=headlist[j];k;k=edge[k].nex) indo[edge[k].to]--;
			    break;
			}
		}
	}
	while(!tuop.empty()){
		int now=tuop.front();
		tuop.pop();
		fen C=point[now]/outdo[now];
		for(int k=headlist[now];k;k=edge[k].nex){
			int v=edge[k].to;
			point[v]=point[v]+C;
		}
	}
	for(int i=1;i<=edsum[0];i++) cout<<point[edsum[i]];
	fclose(stdin);
	fclose(stdout);
	return 0;
}
2020/12/19 17:01
加载中...