实现方法神奇
把每条边拆成长度为\(1\)的正向边和长度为\(-1\)的反向边，那么这张图中如果出现了环，那么这个环的长度在模答案意义下一定是\(0\)，也就是说环长是答案的倍数。那么最大答案就是所有环长度的gcd，最小答案是最大答案的不小于\(3\)的最小约数。
如果没有找到环，那么最大答案就是每个连通块的最长链长度之和，最小答案\(3\)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
// <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; } |
说点什么