栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 2997 Black and White

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 2997 Black and White

#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <math.h>using namespace std;const int N=5200;struct edge{int k,data,next;}e[400000];int first[N],d[N],b[102000],times[N];bool bi[N];int n,p1,p2,p3,nn,m,p,q;void addedge(int p,int q,int k){e[++nn].next=first[p];e[nn].k=q;e[nn].data=k;first[p]=nn;}void relax(int p,int q,int k){if (d[q]>d[p]+k){d[q]=d[p]+k;if (bi[q]){bi[q]=false;++p3;++p2;if (p2==100000) p2=1;b[p2]=q;}}}void spfa(){memset(bi,true,sizeof(bi));memset(d,10,sizeof(d));memset(times,0,sizeof(times));for (int i=1;i<=n;++i){ b[i]=i;bi[i]=false;times[i]=1;}p3=p2=n;p1=1;while (p3 && bi[0]){for (int i=first[b[p1]];bi[0] && i;i=e[i].next) relax(b[p1],e[i].k,e[i].data);bi[b[p1]]=true;++p1;if (p1==100000) p1=1;--p3;}}int gcd(int p,int q){if (q==0) return p;return (gcd(q,p%q));}int lcm(int p,int q){int tmp=gcd(p,q);return p*q/tmp;}int z[N],low[N],now[N],id[N];bool flag[N];int mm,sum;void dfs(int k){bi[k]=false;z[++z[0]]=k;flag[k]=true;low[k]=now[k]=(++mm);for (int i=first[k];i;i=e[i].next){if (bi[e[i].k]) dfs(e[i].k);if (flag[e[i].k]) low[k]=min(low[k],low[e[i].k]);}if (low[k]==now[k]){++sum;while (z[z[0]+1]!=k){ flag[z[z[0]]]=false;id[z[z[0]--]]=sum;}}} int main(){while (scanf("%d%d%d",&n,&p,&q)==3){if (lcm(p,q)<=n+1){puts("NO");continue;}memset(first,0,sizeof(first));nn=0;n++;for (int i=1;i<=n-p;++i){ addedge(i+p,i,-1);}for (int i=1;i<=n-q;++i){ addedge(i,i+q,-1);}mm=sum=0;memset(bi,true,sizeof(bi));memset(flag,false,sizeof(flag));for (int i=1;i<=n;++i) if (bi[i]) dfs(i);if (sum!=n){puts("NO");continue;}spfa();puts("YES");for (int i=2;i<n;++i) printf("%d ",d[i]-d[i-1]);printf("%dn",d[n]-d[n-1]);}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/374768.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号