题目大意:给定n个人,分别戴着k类面具(k>=3,k未知),其中戴着i类面具的人能看见第i%k+1类人的面具,给定一些人互相看到的关系,求k的最大最小值
题解见 http://www.cnblogs.com/proverbs/archive/2013/01/17/2865093.html
DFS求环长度
注意当图中不存在环时k的最大值为所有连通图中最长链的长度之和
正边权值为+1 负边权值为-1 算GCD时要注意取绝对值
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 100100 using namespace std; struct abcd{ int to,f,next; }table[1001001]; int head[M],f[M],tot=1; int n,m,ansmax,ansmin,lmax,lmin; bool v[M]; int GCD(int x,int y) { if(y==0) return x; return GCD(y,x%y); } void dfs1(int x) { int i; v[x]=1; for(i=head[x];i;i=table[i].next) { if(!v[table[i].to]) f[table[i].to]=f[x]+table[i].f,dfs1(table[i].to); else ansmax=GCD(ansmax, abs(f[x]+table[i].f-f[table[i].to]) ); } } void dfs2(int x) { int i; v[x]=1; lmax=max(lmax,f[x]); lmin=min(lmin,f[x]); for(i=head[x];i;i=table[i].next) if(!v[table[i].to]) { f[table[i].to]=f[x]+table[i].f; dfs2(table[i].to); } } void add(int x,int y,int z) { table[++tot].to=y; table[tot].f=z; table[tot].next=head[x]; head[x]=tot; } int main() { freopen("party.in","r",stdin); freopen("party.out","w",stdout); int i,x,y; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y,1); add(y,x,-1); } for(i=1;i<=n;i++) if(!v[i]) dfs1(i); if(ansmax) for(ansmin=3;ansmin<ansmax&&ansmax%ansmin;ansmin++); else { memset(v,0,sizeof v); memset(f,0,sizeof f); for(i=1;i<=n;i++) if(!v[i]) { lmax=lmin=0; dfs2(i); ansmax+=lmax-lmin+1; } ansmin=3; } if(ansmax<3) ansmax=ansmin=-1; printf("%d %d\n",ansmax,ansmin); }