BZOJ1064 NOI2008假面舞会

挺神的这题，发现只有环和链两种情况

搜索时我们只考虑环的，因为链可以看成找不到分类的环。

当成链时大小是的最大值是各链长的和，最小值是3

当成环时最大值是各环长的gcd，最小值是大于3的最小的ans的约数

当有链有环时只有当环的gcd大于等于3时才有解，所以我们统计答案时要优先考虑环的情况，考虑链情况时当且仅当没有环

By：大奕哥

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e5+;

 int n,m,ans,ans2,pos[N],head[N],cnt,ma[N],mi[N],f[N];

 bool v[N];

 struct node{

     int to,nex,w;

 }e[];

 void add(int x,int y,int w)

 {

     e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;e[cnt].w=w;

 }

 int gcd(int a,int b){return b==?a:gcd(b,a%b);}

 int get(int x){return x==f[x]?x:f[x]=get(f[x]);}

 void dfs(int x,int tmp)

 {

     ma[tmp]=max(ma[tmp],pos[x]);

     mi[tmp]=min(mi[tmp],pos[x]);v[x]=;

     for(int i=head[x];i;i=e[i].nex)

     {

         int y=e[i].to;

         if(!v[y])

         {

             pos[y]=pos[x]+e[i].w;

             dfs(y,tmp);

         }

         else ans=gcd(ans,abs(pos[x]-pos[y]+e[i].w));

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);int x,y;

     for(int i=;i<=n;++i)f[i]=i;

     for(int i=;i<=m;++i)

     {

         scanf("%d%d",&x,&y);

         add(x,y,);add(y,x,-);

         int fx=get(x),fy=get(y);

         f[fx]=fy;

     }

     memset(mi,0x3f,sizeof(mi));

     for(int i=;i<=n;++i)

         if(!v[i]){

             dfs(i,get(i));

         }

     if(ans<)

     {

         if(!ans)

         for(int i=;i<=n;++i)

         if(f[i]==i)

         ans+=ma[i]-mi[i]+;

         if(ans<)printf("-1 -1");

         else

         printf("%d 3",ans);

     }

     else

     {

         for(int i=;i<=ans&&!ans2;++i)

         if(ans%i==)ans2=i;

         printf("%d %d",ans,ans2);

     }

     return ;

 }