bzoj 1064 假面舞会 图论？？+dfs

本文主要是介绍bzoj 1064 假面舞会 图论？？+dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有两种情况需要考虑

1.链:可以发现对最终的k没有影响

2.环:如果是真环(即1->2->3->4->1)，可以看出所有可行解一定是该环的因数

 假环呢??(1->2->3->4,1->5->4),可行解便是两条路的差值的因数

So??对于每条边，正建1，反建-1，dfs，每出一个环，就计算gcd

没有环呢？？最小是3，最大是所有链加和喽

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 100005
using namespace std;
int Gcd,n,m,e=1,head[N],dep[N],maxn,minn,len;
bool flag[N];
struct edge{int v,w,next;
}ed[2000500];
int gcd(int x,int y){return y==0?x:gcd(y,x%y);
}
int abs(int x){return x>0?x:-x;
}
void add(int u,int v,int w){ed[e].v=v; ed[e].w=w;ed[e].next=head[u];head[u]=e++;
}
void dfs(int x,int k){flag[x]=1; dep[x]=k;maxn=max(maxn,k);minn=min(minn,k);for(int i=head[x];i;i=ed[i].next){int v=ed[i].v,w=ed[i].w;if(!flag[v]) dfs(v,k+w);else  Gcd=gcd(Gcd,abs(dep[v]-k-w));}
}
int main()
{int u,v;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);add(u,v,1); add(v,u,-1);}for(int i=1;i<=n;i++){if(!flag[i]){maxn=-0x7fffffff;minn=0x7fffffff;dfs(i,1);len+=maxn-minn+1;}}if(Gcd==0){if(len<3) printf("-1 -1");else printf("%d 3\n",len);}else{if(Gcd<3) printf("-1 -1");else{int i;for(i=3;i<=Gcd&&Gcd%i!=0;i++){}printf("%d %d\n",Gcd,i);}}return 0;
}

这篇关于bzoj 1064 假面舞会 图论？？+dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---