【BZOJ1064】【NOI2008】假面舞会

实现方法神奇

把每条边拆成长度为\(1\)的正向边和长度为\(-1\)的反向边，那么这张图中如果出现了环，那么这个环的长度在模答案意义下一定是\(0\)，也就是说环长是答案的倍数。那么最大答案就是所有环长度的gcd，最小答案是最大答案的不小于\(3\)的最小约数。

如果没有找到环，那么最大答案就是每个连通块的最长链长度之和，最小答案\(3\)。

// <1064.cpp> - Thu Mar  9 11:15:48 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
#define next NEXT
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=100010;
const int MAXM=4000010;
const int INF=1e9;
int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM];
inline void add(int x,int y,int z){next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;}
int ans,dis[MAXN],mi[MAXN],ma[MAXN];
bool vis[MAXN];
void dfs(int x,int r){
    vis[x]=1;
    mi[r]=min(mi[r],dis[x]);
    ma[r]=max(ma[r],dis[x]);
    for(int i=b[x];i;i=next[i])
        if(vis[to[i]])ans=__gcd(ans,abs(dis[x]+val[i]-dis[to[i]]));
        else{
            dis[to[i]]=dis[x]+val[i];
            dfs(to[i],r);
        }
}
int main(){
    int n=gi(),m=gi();
    for(int i=1;i<=m;i++){
        int x=gi(),y=gi();
        add(x,y,1);add(y,x,-1);
    }
    int li=0;
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        dfs(i,i);
        li+=ma[i]-mi[i]+1;
    }
    if(!ans){
        if(li<3)printf("-1 -1");
        else printf("%d %d",li,3);
        return 0;
    }
    if(ans<3){printf("-1 -1");return 0;}
    for(int i=3;i<=ans;i++)if(!(ans%i)){printf("%d %d",ans,i);break;}
    return 0;
}

// <1064.cpp> - Thu Mar 9 11:15:48 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

#define next NEXT

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=100010;

const int MAXM=4000010;

const int INF=1e9;

int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM];

inline void add(int x,int y,int z){next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;}

int ans,dis[MAXN],mi[MAXN],ma[MAXN];

bool vis[MAXN];

void dfs(int x,int r){

vis[x]=1;

mi[r]=min(mi[r],dis[x]);

ma[r]=max(ma[r],dis[x]);

for(int i=b[x];i;i=next[i])

if(vis[to[i]])ans=__gcd(ans,abs(dis[x]+val[i]-dis[to[i]]));

else{

dis[to[i]]=dis[x]+val[i];

dfs(to[i],r);

}

int main(){

int n=gi(),m=gi();

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

int x=gi(),y=gi();

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

}

int li=0;

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

if(vis[i])continue;

dfs(i,i);

li+=ma[i]-mi[i]+1;

}

if(!ans){

if(li<3)printf("-1 -1");

else printf("%d %d",li,3);

return 0;

}

if(ans<3){printf("-1 -1");return 0;}

for(int i=3;i<=ans;i++)if(!(ans%i)){printf("%d %d",ans,i);break;}

return 0;

}