NOI2008假面舞会

Posted on By 二价氢

题目大意,给你一个图,但这个图不一定完整,要你给出这个图补全之后且所有的环直径相等时,这个直径的最大值和最小值(>3)

上图为样例对应图

显然,直径的最大值与最小值都为4

那么,我们有两种算法:

1、缩点法,即,将同类顶点放在一起,最后我们得到的每一个联通分量可能为环或树,最后答案很简单就能得出,缺点是过程略复杂

2、找环法,即,我们从没一个节点找下去,找到一个个的环,最后,这个环就是答案

推荐题解:BYVoid

……及他的讲义:这里下载

下面是AC-Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=754198782;    //<---------Rand()
const int MAXN=100005,MAXM=1000005;
struct edge{int next,op,t,w;bool del;}E[MAXM];//邻接表,反向边,终点,权值,233
int Vf[MAXN],Vl[MAXN],Vit[MAXN],Vbl[MAXN];
bool Vvis[MAXN];
int C[MAXN],CirCnt;//环大小,环数
int BMin[MAXN],BMax[MAXN];
int N,M,totE,D;
int abs(int x)
{
    return (x<0)?-x:x;
}
int gcd(int a,int b)
{
    return (b)?(gcd(b,a%b)):a;
}
int addedge(int u,int v,int w)
{
    if (Vl[u])
        Vl[u]=E[Vl[u]].next=++totE;
    else
        Vf[u]=Vl[u]=++totE;
    E[totE].t=v;
    E[totE].w=w;
    return totE;
}
void init()
{
    int tta,ttb,noa,nob;
    scanf("%d%d",&N,&M);
    for (int i=1;i<=M;i++)
    {
        scanf("%d%d",&tta,&ttb);
        noa=addedge(tta,ttb,1);
        nob=addedge(ttb,tta,-1);
        E[nob].op=noa;
        E[noa].op=nob;
    }
}
void findcircle(int u,int it)
{
    Vit[u]=it;
    Vvis[u]=true;
    for (int i=Vf[u];i;i=E[i].next)
    {
        if(E[i].del)
            continue;
        E[i].del=true;
        E[E[i].op].del=true;
        if (!Vvis[E[i].t])
        {
            findcircle(E[i].t,it+E[i].w);
        }else
        {
            if ((it+E[i].w-Vit[E[i].t])!=0)
            {
                C[++CirCnt]=abs(it+E[i].w-Vit[E[i].t]);
            }
        }
    }
}
void findpart(int u)
{
    Vbl[u]=D;
    for (int i=Vf[u];i;i=E[i].next)
        if (!Vbl[E[i].t])
            findpart(E[i].t);
}
void part()
{
    for (int i=1;i<=N;i++)
        if (!Vbl[i])
        {
            D++;
            findpart(i);
            BMin[D]=INF;
            BMax[D]=-INF;
        }
}
void longest(int u,int it)
{
    Vit[u]=it;
    Vvis[u]=true;
    for (int i=Vf[u];i;i=E[i].next)
    {
        if (E[i].del)
            continue;
        E[i].del=E[E[i].op].del=true;
        longest(E[i].t,it+E[i].w);
    }
}
void link()
{
    memset(Vvis,0,sizeof(Vvis));
    for (int i=1;i<=N;i++)
        for (int j=Vf[i];j;j=E[j].next)
            E[j].del=E[E[j].op].del=false;
    for (int i=1;i<=N;i++)
    {
        if (!Vvis[i])
            longest(i,1);
        BMax[Vbl[i]]=max(BMax[Vbl[i]],Vit[i]);
        BMin[Vbl[i]]=min(BMin[Vbl[i]],Vit[i]);
    }
    int Gans=0,Mans=0;
    for (int i=1;i<=D;i++)
        Gans+=BMax[i]-BMin[i]+1;
    if (Gans<3)
    {
        printf("-1 -1\n");
        return;
    }else
    {
        printf("%d 3\n",Gans);
    }
}
void solve()
{
    int i,GCD,LCD,MIN;
    memset(Vvis,0,sizeof(Vvis));
    for (i=1;i<=N;i++)
        if (!Vvis[i])
            findcircle(i,1);
    MIN=GCD=C[1];
    for (i=2;i<=CirCnt;i++)
    {
        GCD=gcd(GCD,C[i]);
        MIN=min(MIN,C[i]);
    }
    for (LCD=3;LCD<=MIN;LCD++)
    {
        for (i=1;i<=CirCnt;i++)
            if (C[i]%LCD!=0)
                break;
        if (i>CirCnt)
            break;
    }
    if (CirCnt==0)
    {
        part();
        link();
    }
    else if (GCD>=3)
    {
        printf("%d %d\n",GCD,LCD);
    }else
    {
        printf("-1 -1\n");
    }
}
int main()
{
    init();
    solve();
    return 0;
}