正題

題目鏈接:https://www.luogu.org/problem/P1477

---

題目大意

一張有向圖，分為$z$類點(diǎn)，對(duì)于每條邊要么是$i$類連向$i+1$類，要么是$k$類連向$1$類($k\ge 3$)，求$z$的最小值和最大值(不給出$k$)

---

解題思路

首先不考慮環(huán)，那么最大值就是每張圖中最長鏈的長度和，最小值就是$3$，因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$1?>2?>3?>1...$就好了。

若有環(huán)，最大值就是每個(gè)環(huán)大小的$gcd$，因?yàn)閷?duì)于每個(gè)環(huán)都要分成若干個(gè)相同長度的循環(huán)節(jié)，然后最小值就是最大值的一個(gè)最小的因子(要$\ge 3$)，因?yàn)檫@是可以分成的最小循環(huán)節(jié)。

$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); }

總結(jié)

以上是生活随笔為你收集整理的P1477-[NOI2008]假面舞会【构图,dfs,gcd】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。