莫名其妙的dfs算法。
1.这道题首先要推出来,如果有弓形或者环形,答案必须是环长度和弓形俩条路长度之差的约数。
而且如果你直接按照原图来建图你是跑不出来的。
1.如果你每个点访问一次时dfs所有点,tle。
2.如果你打vis标记,你判断不出来弓形,wa。
3.如果妄图用一个in数组记录哪个点in[u]=0,然后从这个点开始跑的话。整体做个环,甩出去个头支的。wa+奇奇怪怪的错误。
所以我们要求每个点逆向也可以跑。
所以建图为 a->b 1,b->a->-1。
这样上述问题就不会出现了。
2.如果没有上述情况,肯定就是个dag图。跑dfs就行了。
然后求最多可能有多少类面具的答案为sum(最长链的长度)。用心去感受
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; const int maxn = 100000 + 10; const int maxm = 4000000 + 10; const int inf = 0x3f3f3f3f; int g[maxn],v[maxm],next[maxm],dist[maxm],eid; int c[maxn]; bool vis[maxn],inque[maxn],mark; int n,m,ans,l,r,minres,maxres,u; queue<int> q; void addedge(int a,int b,int c) { v[eid]=b; dist[eid]=c; next[eid]=g[a]; g[a]=eid++; } int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } void dfs(int u,int fa,int d) { if(vis[u]) { ans=gcd(ans,abs(d-c[u])); return; } vis[u]=1; c[u]=d; for(int i=g[u];~i;i=next[i]) if(v[i]!=fa) dfs(v[i],u,c[u]+dist[i]); } void build() { memset(g,-1,sizeof(g)); scanf("%d%d",&n,&m); for(int i=1,a,b;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b,1); addedge(b,a,-1); } } void spfa(int u) { inque[u]=1; l=min(l,c[u]); r=max(r,c[u]); for(int i=g[u];~i;i=next[i]) if(!inque[v[i]]) { c[v[i]]=c[u]+dist[i]; spfa(v[i]); } } void solve() { for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0,0); if(ans&&ans<=2) { printf("-1 -1\n"); return; } if(ans) { maxres=ans; for(int i=3;i<=maxres;i++) if(maxres%i==0) { minres=i; break; } } else for(int i=1;i<=n;i++) if(!inque[i]) { l=r=c[i]=0; spfa(i); maxres+=r-l+1; minres=3; } if(maxres<3) maxres=minres=-1; printf("%d %d\n",maxres,minres); } int main() { build(); solve(); return 0; }