国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > HDU 3639 Hawk-and-Chicken (强连通分量+树形DP)

HDU 3639 Hawk-and-Chicken (强连通分量+树形DP)

来源:程序员人生   发布时间:2015-03-20 08:58:02 阅读次数:2197次

题目地址:HDU 3639

先用强连通份量缩点,缩点以后,再重新按缩点以后的块逆序构图,每一个块的值是里边缩的点的个数,那末得到选票的最大的1定是重新构图后入度为0的块,然后求出来找最大值便可。

代码以下:

#include <iostream> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include <stdlib.h> #include <map> #include <set> #include <stdio.h> using namespace std; #define LL long long #define pi acos(⑴.0) const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e⑼; const int MAXN=5000+10; const int MAXM=30000+10; int head[MAXN], cnt, low[MAXN], dfn[MAXN], belong[MAXN], instack[MAXN], stk[MAXN], dp[MAXN]; int ans, indx, top; struct node { int u, v, next; }edge[MAXM]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void tarjan(int u) { low[u]=dfn[u]=++indx; instack[u]=1; stk[++top]=u; for(int i=head[u];i!=⑴;i=edge[i].next){ int v=edge[i].v; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ ans++; while(1){ int v=stk[top--]; belong[v]=ans; dp[ans]++; instack[v]=0; if(u==v) break; } } } void init() { memset(head,⑴,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(instack,0,sizeof(instack)); memset(dp,0,sizeof(dp)); cnt=ans=indx=top=0; } int head1[MAXN], cnt1, vis[MAXN], in[MAXN], max1, sum; struct node1 { int u, v, next; }edge1[MAXM]; void add1(int u, int v) { edge1[cnt1].v=v; edge1[cnt1].next=head1[u]; head1[u]=cnt1++; } void dfs(int u) { vis[u]=1; sum+=dp[u]; for(int i=head1[u];i!=⑴;i=edge1[i].next){ int v=edge1[i].v; if(!vis[v]){ dfs(v); } } } void init1() { memset(head1,⑴,sizeof(head1)); memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); cnt1=0; max1=0; } int c[MAXN], tot, d[MAXN]; int main() { int t, n, m, i, j, u, v, Case=0; scanf("%d",&t); while(t--){ Case++; scanf("%d%d",&n,&m); init(); while(m--){ scanf("%d%d",&u,&v); add(u,v); } for(i=0;i<n;i++){ if(!dfn[i]) tarjan(i); } init1(); for(i=0;i<n;i++){ for(j=head[i];j!=⑴;j=edge[j].next){ if(belong[i]!=belong[edge[j].v]){ add1(belong[edge[j].v],belong[i]); in[belong[i]]++; } } } memset(d,⑴,sizeof(d)); for(i=1;i<=ans;i++){ if(!in[i]){ sum=0; memset(vis,0,sizeof(vis)); dfs(i); d[i]=sum; max1=max(max1,d[i]); } } tot=0; for(i=0;i<n;i++){ if(d[belong[i]]==max1) c[tot++]=i; } printf("Case %d: %d ",Case, max1⑴); for(i=0;i<tot;i++){ printf("%d",c[i]); if(i!=tot⑴) printf(" "); } puts(""); } return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生