BZOJ-1064: [Noi2008]假面舞会

[文章目录]

Description

每个面具都有一个编号,主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感,主办方把面具分为k (k≥3)类,并使用特殊的技术将每个面具的编号标在了面具上,只有戴第i 类面具的人才能看到戴第i+1 类面具的人的编号,戴第k 类面具的人能看到戴第1 类面具的人的编号。 参加舞会的人并不知道有多少类面具,但是栋栋对此却特别好奇,他想自己算出有多少类面具,于是他开始在人群中收集信息。 栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第2号面具的人看到了第5 号面具的编号。栋栋自己也会看到一些编号,他也会根据自己的面具编号把信息补充进去。由于并不是每个人都能记住自己所看到的全部编号,因此,栋栋收集的信 息不能保证其完整性。现在请你计算,按照栋栋目前得到的信息,至多和至少有多少类面具。由于主办方已经声明了k≥3,所以你必须将这条信息也考虑进去。n<=10^5 m<=10^6

如果有环的话,所有环长的gcd即为答案。如果无环,联通的拓扑图的最长链上点的个数的和加上即为答案。

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
const int inf=0x3f3f3f3f;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
    return x;
}
int n,m,sum,cir,head[N],to[2001000],nxt[2001000],f[2001000],cnt;
inline void add(int x,int y,int z)
{
    to[++cnt]=y; nxt[cnt]=head[x];
    head[x]=cnt; f[cnt]=z;
}
inline int Abs(int x){return x>0?x:-x;}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
queue<int>q;
int dis[N],b[N],mi,mx;
bool vis[N];
void bfs(int x)
{
    vis[x]=1; q.push(x); int i; mx=mi=0;
    while(!q.empty())
    {
        x=q.front(); q.pop(); mi=min(mi,dis[x]); mx=max(mx,dis[x]);
        for(i=head[x];i;i=nxt[i])
        {
            if(!vis[to[i]]) vis[to[i]]=1,dis[to[i]]=dis[x]+f[i],q.push(to[i]);
            else cir=gcd(cir,Abs(dis[x]+f[i]-dis[to[i]]));
        }
    }
}
int main()
{
    n=read(); m=read();
    int i,x,y;
    for(i=1;i<=m;++i)
    {
        x=read(); y=read();
        add(x,y,1); add(y,x,-1);
    }
    for(i=1;i<=n;++i) if(!vis[i]) bfs(i),sum+=mx-mi+1;
    if(!cir)
    {
        if(sum>=3) printf("%d 3\n",sum);
        else puts("-1 -1");
    }
    else
    {
        for(y=3;y<=cir;++y) if(cir%y==0) break;
        if(cir>=3) printf("%d %d\n",cir,y);
        else puts("-1 -1");
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注