题意: n个别墅以及一个主建筑楼，从每个别墅都有很多种不同方式走到主建筑楼，其中不同的定义是（每条边可以走多次，如果走边的顺序有一条不同即称两方式不同）。 询问最多的不同方式是多少，以及有多少个别墅有这么多方式，按照顺序输出别墅编号。 如果最多不同方式超过了36500那么都视作zawsze 解析: 容易想到把边反向，问题转化成求从主建筑楼走向各个点的方案数。 对于一个强连通分量，显然我们可以看做是一个点，，所以首先把图缩点。 缩点之后 我们设表示走到第i个点的方案数。 显然 并且特别注意的是，初始时，f[belong[主建筑]]=1。 其次任意一个对于任意一个siz[i]>1的点来说，如果f[i]>0的话，那么显然有无数种走法，直接设为maxn+1。 然后我们观察这其实就是个拓扑图上做DP的过程。 直接拓扑图上DP。 最后扫一遍统计解即可。 复杂度:O(常数*n)； 代码:
;int n,m,rev_cnt;int rev_head[N];struct Line{int x,y;}l[N];struct node{int from,to,next;}rev_edge[N];void init(){memset(rev_head,-1,sizeof(rev_head));rev_cnt=1;}void edgeadd(int from,int to,node *edge,int *head,int &cnt){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}int deep[N],low[N],sta[N],ins[N],belong[N],top,cnt_block,tot;void tarjan(int now){deep[now]=low[now]=++tot;sta[++top]=now,ins[now]=1;for(int i=rev_head[now];i!=-1;i=rev_edge[i].next){int to=rev_edge[i].to;if(!deep[to]){tarjan(to);low[now]=min(low[now],low[to]);}else if(ins[to])low[now]=min(low[now],deep[to]);}if(deep[now]==low[now]){cnt_block++;int t=-1;do{t=sta[top–];ins[t]=0;belong[t]=cnt_block;}while(t!=now);}}bool tag[N];int in[N];void re_build(){for(int i=1;i<=m;i++){int x=l[i].x,y=l[i].y;if(belong[x]==belong[y]){tag[belong[x]]=1;continue;}edgeadd(belong[x],belong[y],rev_edge,rev_head,rev_cnt);in[belong[y]]++;}}int f[N];void Topsort(){queue<int>q;for(int i=1;i<=cnt_block;i++)if(!in[i])q.push(i);f[belong[n]]=1;if(tag[belong[n]])f[belong[n]]+=maxn;while(!q.empty()){int u=q.front();q.pop();for(int i=rev_head[u];i!=-1;i=rev_edge[i].next){int to=rev_edge[i].to;f[to]+=f[u];if(f[to]>maxn)f[to]=maxn+1;in[to]–;if(!in[to]){if(tag[to]&&f[to]>0)f[to]=maxn+1;q.push(to);}}}}void calc(){int ans=-1;top=0;for(int i=1;i<n;i++)if(f[belong[i]]>ans)ans=f[belong[i]];for(int i=1;i<n;i++)if(f[belong[i]]==ans)sta[++top]=i;printf(ans==maxn+1?”zawsze\n”:”%d\n”,ans);printf(“%d\n”,top);for(int i=1;i<=top;i++)printf(“%d “,sta[i]);puts(“”);}int main(){#ifndef ONLINE_JUDGEfreopen(“1512.in”,”r”,stdin);freopen(“1512.out”,”w”,stdout);#endifinit();scanf(“%d%d”,&n,&m);n++;for(int i=1;i<=m;i++){int x,y;scanf(“%d%d”,&x,&y);swap(x,y);edgeadd(x,y,rev_edge,rev_head,rev_cnt);l[i].x=x,l[i].y=y;}for(int i=1;i<=n;i++)if(!deep[i])tarjan(i);init();re_build();Topsort();calc();#ifndef ONLINE_JUDGEfclose(stdin);fclose(stdout);;}
将来靠自己双掌;愿你用双掌开拓出美好的梦想。
