正题

题目链接:https://www.luogu.org/problem/P1477

---

题目大意

一张有向图，分为$z$类点，对于每条边要么是$i$类连向$i+1$类，要么是$k$类连向$1$类($k\ge 3$)，求$z$的最小值和最大值(不给出$k$)

---

解题思路

首先不考虑环，那么最大值就是每张图中最长链的长度和，最小值就是$3$，因为$1->2->3->1...$就好了。

若有环，最大值就是每个环大小的$gcd$，因为对于每个环都要分成若干个相同长度的循环节，然后最小值就是最大值的一个最小的因子(要$\ge 3$)，因为这是可以分成的最小循环节。

$dfs$找就好了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; struct node{int to,next,w; }a[20*N]; int n,m,ans,minans,maxans,dis[N],ls[N],tot; bool v[N]; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w; } void circle(int x) {v[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y]) ans=__gcd(ans,abs(dis[x]-dis[y]+a[i].w));else dis[y]=dis[x]+a[i].w,circle(y);} } void line(int x) {v[x]=1;minans=min(minans,dis[x]);maxans=max(maxans,dis[x]);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y]) continue;dis[y]=dis[x]+a[i].w;line(y);} } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y,1);addl(y,x,-1);}for(int i=1;i<=n;i++)if(!v[i]) circle(i);if(ans){if(ans<3){printf("-1 -1\n");return 0;}for(int i=3;i<=ans;i++)if(!(ans%i)){minans=i;break;}printf("%d %d\n",ans,minans);return 0;}memset(dis,0,sizeof(dis));memset(v,0,sizeof(v));for(int i=1;i<=n;i++)if(!v[i]){minans=maxans=0;line(i);ans+=maxans-minans+1;}if(ans<3) printf("-1 -1\n");else printf("%d 3\n",ans); }

总结

以上是生活随笔为你收集整理的P1477-[NOI2008]假面舞会【构图,dfs,gcd】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。