求助,为什么最后两个点WA了
查看原帖
求助,为什么最后两个点WA了
77615
OIerAlbedo楼主2021/3/25 08:21
#include<bits/stdc++.h>
using namespace std;
unsigned long long yu,j,cnt,n,m,t,w,i,e[200000];
int f2[10000000],a[400000],b[400000],d[400000],f[400000];
long double p1[200000],p2[200000];
long double o3,o4,o1,o2,x,y,xx,yy,z;
long double gcd(long double x,long double y)
{
    if (y==0) return x;
    long double ans=gcd(y,x-((unsigned long long)(x/y)*y));return ans;
}
void add(int x,int y)
{
    cnt++;a[cnt]=y;b[cnt]=d[x];d[x]=cnt;
}
int main()
{
    cin>>n>>m;
    t=1;
    for (i=1;i<=n;i++)
        {
                   cin>>e[i];
                   for (j=1;j<=e[i];j++)
                       {
                           cin>>yu;
                           add(i,yu);f[yu]++;
                       }
        }
    for (i=1;i<=n;i++)
        if (f[i]==0)
           {
           w++;f2[w]=i;p1[i]=1;p2[i]=1;
           }
    while (t<=w)
        {
            for (i=d[f2[t]];i;i=b[i])
                  {
                      x=p1[f2[t]];y=p2[f2[t]];z=e[f2[t]];
                      y=y*z;z=gcd(x,y);x/=z;y/=z;
                      xx=p1[a[i]];yy=p2[a[i]];
                      if ((xx!=0)&(yy!=0))
                          {
                          z=y/gcd(y,yy)*yy;
                          o1=x*z/y;o2=xx*z/yy;
                          o1=o1+o2;
                      y=z;x=o1;z=gcd(x,y);x/=z;y/=z;
                      }
                      p1[a[i]]=x;p2[a[i]]=y;f[a[i]]--;
                      if (f[a[i]]==0)
                         {
                             w++;f2[w]=a[i];
                         }
                  }
            t++;
        }
    while (t<=w)
        {
            for (i=d[f2[t]];i;i=b[i])
                  {
                      x=p1[f2[t]];y=p2[f2[t]];z=e[f2[t]];
                      y=y*z;z=gcd(x,y);x/=z;y/=z;
                      xx=p1[a[i]];yy=p2[a[i]];
                      if ((xx!=0)&(yy!=0))
                          {
                          z=y/gcd(y,yy)*yy;
                          o3=gcd(x,y);
                          x/=o3;y/=o3;
                          o4=gcd(xx,yy);
                          xx/=o4;yy/=o4;
                          o1=x*z/y;o2=xx*z/yy;
                          o1=o1+o2;
                      y=z;x=o1;z=gcd(x,y);x/=z;y/=z;
                      }
                      p1[a[i]]=x;p2[a[i]]=y;f[a[i]]--;
                      if (f[a[i]]==0)
                         {
                             w++;f2[w]=a[i];
                         }
                  }
            t++;
        }
    for (i=1;i<=n;i++)
       if (e[i]==0)
          printf("%.0Lf %.0Lf\n",p1[i],p2[i]);
    return 0;
}
2021/3/25 08:21
加载中...