做pc端网站怎么样,免费学高中课程的软件,软件设计是干什么的,wordpress 4.5 中文版正题
题目链接:https://www.luogu.org/problem/P1477 题目大意
一张有向图#xff0c;分为zzz类点#xff0c;对于每条边要么是iii类连向i1i1i1类#xff0c;要么是kkk类连向111类(k≥3k\geq 3k≥3)#xff0c;求zzz的最小值和最大值(不给出kkk) 解题思路
首先不考虑环分为zzz类点对于每条边要么是iii类连向i1i1i1类要么是kkk类连向111类(k≥3k\geq 3k≥3)求zzz的最小值和最大值(不给出kkk) 解题思路
首先不考虑环那么最大值就是每张图中最长链的长度和最小值就是333因为1−2−3−1...1-2-3-1...1−2−3−1...就好了。
若有环最大值就是每个环大小的gcdgcdgcd因为对于每个环都要分成若干个相同长度的循环节然后最小值就是最大值的一个最小的因子(要≥3\geq 3≥3)因为这是可以分成的最小循环节。
dfsdfsdfs找就好了。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
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].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;
}
void circle(int x)
{v[x]1;for(int ils[x];i;ia[i].next){int ya[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;minansmin(minans,dis[x]);maxansmax(maxans,dis[x]);for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y]) continue;dis[y]dis[x]a[i].w;line(y);}
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y,1);addl(y,x,-1);}for(int i1;in;i)if(!v[i]) circle(i);if(ans){if(ans3){printf(-1 -1\n);return 0;}for(int i3;ians;i)if(!(ans%i)){minansi;break;}printf(%d %d\n,ans,minans);return 0;}memset(dis,0,sizeof(dis));memset(v,0,sizeof(v));for(int i1;in;i)if(!v[i]){minansmaxans0;line(i);ansmaxans-minans1;}if(ans3) printf(-1 -1\n);else printf(%d 3\n,ans);
}
