题目大意,给你一个图,但这个图不一定完整,要你给出这个图补全之后且所有的环直径相等时,这个直径的最大值和最小值(>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;
}