40 pts求找错
查看原帖
40 pts求找错
401987
yscc楼主2022/5/12 22:51
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,d[100005],a[1000005],a1[1000005],g[1000005],sum[1000005];
ll ver[1000005],p[1000005],q[1000005],Next[1000005],head[1000005],tot;
inline ll gcds(ll a,ll b){
  return b==0?a:gcds(b,a%b);
}
void adds(int x,ll ps,ll qs){
  if(0==q[x]){p[x]=ps,q[x]=qs; return;}
  if(0==qs) return;
  ll gcdss=gcds(q[x],qs);
  p[x]=qs/gcdss*p[x]+q[x]/gcdss*ps;
  q[x]=qs/gcdss*q[x];
  gcdss=gcds(p[x],q[x]);
  p[x]/=gcdss,q[x]/=gcdss;
  return;
}
void add(int x,int y)
{
  ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void bfs()
{
  queue<int> am;
  for(int i=1;i<=m;i++)
    {
      am.push(i);
      p[i]=q[i]=1;
    }
  while(!am.empty())
      {
	int now=am.front();
	am.pop();
	for(int i=head[now];i;i=Next[i])
	  {
	    a1[ver[i]]--;
	    if(0==a1[ver[i]]) am.push(ver[i]);
	    adds(ver[i],p[now],q[now]*d[now]);
	  }
      }
}
int main()
{
  //freopen("water.in","r",stdin);
  {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      {
	cin>>d[i];
	for(int j=1;j<=d[i];j++)
	  {
	    cin>>a[j];
	    a1[a[j]]++;
	    add(i,a[j]);
	  }
      }
    bfs();
    for(int i=1;i<=n;i++)
      {
	if(d[i]==0)
	  cout<<p[i]<<" "<<q[i]<<endl;
      }
  }
  //freopen("water.out","w",stdout);
  return 0;
}
2022/5/12 22:51
加载中...