BZOJ 1064 가면 무도회(그림-연통 분량)

제목 링크:http://61.187.179.132/JudgeOnline/problem.php?id=1064
제목:1 년 에 한 번 있 는 가면 무도회 가 또 시작 되 었 고 동 동 도 올해 무도회 에 흥 겹 게 참가 했다.올해 의 가면 은 모두 주최측 이 특별히 맞 춘 것 이다.무도회 에 참가 하 는 모든 사람들 은 입장 할 때 자신 이 좋아 하 는 가면 을 선택 할 수 있다.각 가면 에는 하나의 번호 가 있 는데 주최 측은 이 번 호 를 이 가면 을 가 진 사람 에 게 알려 줄 것 이다.무도 회 를 더욱 신비 감 있 게 하기 위해 주최 측은 가면 을 k(k≥3)류 로 나 누고 특수 한 기술 로 각 가면 의 번 호 를 가면 에 표시 했다.i 류 가면 을 쓴 사람 만 이 i+1 류 가면 을 쓴 사람의 번 호 를 볼 수 있 고 k 류 가면 을 쓴 사람 은 1 류 가면 을 쓴 사람의 번 호 를 볼 수 있다.무도회 에 참가 한 사람들 은 몇 가지 가면 이 있 는 지 모 르 지만 동 동 은 이에 대해 궁금 해 했다.그 는 자신 이 몇 가지 가면 이 있 는 지 계산 하고 싶 어서 사람들 속 에서 정 보 를 수집 하기 시작 했다.동 동이 수집 한 정 보 는 모두 몇 번 째 가면 을 쓴 사람들 이 몇 번 째 가면 의 번 호 를 보 았 다 는 것 이다.2 번 가면 을 쓴 사람 이 5 번 가면 의 번 호 를 보 았 다.동 동 은 자신 도 번 호 를 볼 수 있 고 자신의 가면 번호 에 따라 정 보 를 보충 하기 도 한다.누구나 자신 이 본 번 호 를 모두 기억 할 수 있 는 것 은 아니 기 때문에 동 에서 수집 한 정 보 는 완전 성 을 보장 할 수 없다.지금 은 동 에서 현재 얻 은 정보 에 따라 기껏해야 몇 가지 가면 이 있 는 지 계산 해 보 세 요.주최 측 이 k≥3 을 이미 성명 하 였 기 때문에,너 는 반드시 이 정보 도 고려 해 야 한다.
사고방식:(1)우선 우리 가 가설 한 조건 에 고리 가 존재 한다.그러면 모든 링 의 길이 의 최대 공약수 G 는 가장 많은 가면 종류 이다.3 보다 크 고 가장 작은 것 이 며 G 의 약수 인 가장 적은 가면 종류 이다.G 가 3 보다 작 을 때 풀 리 지 않 음;
(2)링 이 존재 하지 않 는 다 고 가정 하면 모두 방향 체인 이 있다.그러면 모든 연결 블록 의 가장 긴 체인 과 Sum 은 가장 많은 가면 종류 이다.3.가장 적은 가면 종류 다.물론 섬<3 시 는 풀 리 지 않 습 니 다.
다음은 링 과 최 장 체인 을 어떻게 구 하 는 지 입 니 다.링 을 구 하 는 것 은 바로 강 한 연결 분량 이다.가장 긴 체인 은 모든 입 도 를 0 으로 하 는 점 에서 한 번 아래로 계산 할 수 있다(여기 서 점 u 부터 아래로 하 는 가장 긴 체인 을 기록 할 수 있다).그림 을 만 들 때 양 방향 변 을 만 듭 니 다.(x,y,1)과(y,x,-1).(1)우선 고 리 를 찾는다.우 리 는 첫 번 째 로 옮 겨 다 닐 때의 거 리 를 점 마다 기록 하 는 DFS 를 임의로 시작 합 니 다.다음 점 이 이미 옮 겨 다 니 는 점 v 라면 현재 점 u 의 d[u]로 업 데 이 트 된 점 v 의 d 를 p 로 하면 abs(p-d[v])는 링 의 길이 입 니 다.예 를 들 어 1-2-3-4-1 은 링 이 4 이다.그러나 1-2-3-4,1-5-4 에 대해 링 의 크기 는 1 이 고 무 해(마지막 최대 공약 수 는 1)를 얻 을 수 있다.(2)가장 긴 사슬 을 찾는다.어떤 점 에서 부터 DFS 는 사 이 드 를 옮 겨 다 니 는 지 여 부 를 기록 합 니 다.각 사 이 드 와 그 반대 사 이 드 는 한 번 만 옮 겨 다 닙 니 다.그리고 여기 도 d 값 을 기록 합 니 다.이렇게 모든 연결 분량 의 최대 d 값 Max 와 최소 d 값 Min:Max-min+1 은 이 연결 블록 의 가장 긴 체인 길이 입 니 다.
 

struct node

{

    int v,w,next;

};

 

node edges[N<<2];

int head[N];

int e;

 

void Add(int u,int v,int w)

{

    edges[e].v=v;

    edges[e].w=w;

    edges[e].next=head[u];

    head[u]=e++;

}

 

int d[N];

 

int n,m,visit[N];

 

int Gcd(int x,int y)

{

    if(!y) return x;

    return Gcd(y,x%y);

}

int ans;

 

 

void DFS(int u)

{

    visit[u]=1;

    int i,v,w;

    for(i=head[u];i!=-1;i=edges[i].next)

    {

        v=edges[i].v;

        w=edges[i].w;

        if(visit[v])

        {

            ans=Gcd(ans,abs(d[u]+w-d[v]));

        }

        else

        {

            d[v]=d[u]+w;

            DFS(v);

        }

    }

}

 

int Max,Min;

int h[N];

 

void dfs(int u)

{

    visit[u]=1;

    Max=max(Max,d[u]);

    Min=min(Min,d[u]);

    int i,v,w;

    for(i=head[u];i!=-1;i=edges[i].next)

    {

        v=edges[i].v;

        w=edges[i].w;

        if(!h[i])

        {

            h[i]=h[i^1]=1;

            d[v]=d[u]+w;

            dfs(v);

        }

    }

}

 

int main()

{

    clr(head,-1);

    RD(n,m);

    int i,x,y;

    FOR1(i,m)

    {

        RD(x,y);

        Add(x,y,1);

        Add(y,x,-1);

    }

    FOR1(i,n) if(!visit[i]) DFS(i);

    if(ans)

    {

        for(i=3;i<=ans;i++) if(ans%i==0) break;

        if(ans<3) puts("-1 -1");

        else PR(ans,i);

        return 0;

    }

    clr(visit,0);

    int ans=0;

    FOR1(i,n) if(!visit[i]) 

    {

        Max=Min=d[i]=0;

        dfs(i);

        ans+=Max-Min+1;

    }

    if(ans<3) puts("-1 -1");

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

}