首页 > 代码库 > HDU 3639 Hawk-and-Chicken（强连通缩点+反向建图）
HDU 3639 Hawk-and-Chicken（强连通缩点+反向建图）
http://acm.hdu.edu.cn/showproblem.php?pid=3639
题意：
有一群孩子正在玩老鹰抓小鸡，由于想当老鹰的人不少，孩子们通过投票的方式产生，但是投票有这么一条规则：投票具有传递性，A支持B，B支持C，那么C获得2票（A.B共两票），输出最多能获得的票数是多少张和获得最多票数的人是谁？
思路：
先强连通缩点反向建图，在计算强连通的时候，需要保存每个连通分支的结点个数。
为什么要反向建图呢？因为要寻找票数最多的，那么肯定是入度为0的点，然后dfs计算它的子节点的权值（连通分支结点个数）加起来有多少。
注意，最后要减去1，不能把自己也算进去。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #include<cmath> 8 #include<stack> 9 using namespace std; 10 11 const int maxn=5000+5; 12 13 int n,m; 14 int sum; 15 16 vector<int> G[maxn]; 17 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt; 18 int num[maxn]; //记录每个连通分支的结点个数 19 stack<int> S; 20 21 vector<int> rG[maxn]; 22 int in[maxn]; 23 int vis[maxn]; 24 int cnt[maxn]; 25 26 void dfs(int u) { 27 pre[u] = lowlink[u] = ++dfs_clock; 28 S.push(u); 29 for (int i = 0; i < G[u].size(); i++) 30 { 31 int v = G[u][i]; 32 if (!pre[v]) 33 { 34 dfs(v); 35 lowlink[u] = min(lowlink[u], lowlink[v]); 36 } 37 else if(!sccno[v]) 38 lowlink[u] = min(lowlink[u], pre[v]); 39 } 40 if (pre[u] == lowlink[u]) 41 { 42 scc_cnt++; 43 num[scc_cnt]=0; 44 for(;;) 45 { 46 int x = S.top(); S.pop(); 47 sccno[x] = scc_cnt; 48 num[scc_cnt]++; 49 if (x == u) break; 50 } 51 } 52 } 53 54 void find_scc(int n) 55 { 56 dfs_clock = scc_cnt = 0; 57 memset(pre, 0, sizeof(pre)); 58 memset(sccno, 0, sizeof(sccno)); 59 for (int i = 0; i < n; i++) 60 if (!pre[i]) dfs(i); 61 } 62 63 void dfs2(int u) 64 { 65 vis[u]=1; 66 sum+=num[u]; 67 for(int i=0;i<rG[u].size();i++) 68 { 69 int v=rG[u][i]; 70 if(!vis[v]) dfs2(v); 71 } 72 } 73 74 int main() 75 { 76 //freopen("D:\\input.txt","r",stdin); 77 int T; 78 int kase=0; 79 scanf("%d",&T); 80 while(T--) 81 { 82 scanf("%d%d",&n,&m); 83 for(int i=0;i<n;i++) G[i].clear(); 84 while(m--) 85 { 86 int u,v; 87 scanf("%d%d",&u,&v); 88 G[u].push_back(v); 89 } 90 find_scc(n); 91 92 for(int i=1;i<=scc_cnt;i++) rG[i].clear(); 93 memset(in,0,sizeof(in)); 94 for(int u=0;u<n;u++) 95 { 96 for(int i=0;i<G[u].size();i++) 97 { 98 int v=G[u][i]; 99 if(sccno[u]!=sccno[v]) {rG[sccno[v]].push_back(sccno[u]);in[sccno[u]]++;}100 }101 }102 103 int ans=0;104 memset(cnt,0,sizeof(cnt));105 for(int i=1;i<=scc_cnt;i++)106 {107 sum=0;108 if(in[i]==0) //入度为0109 {110 memset(vis,0,sizeof(vis));111 dfs2(i);112 cnt[i]=sum-1; //需要减1，因为它自己所处的连通分支得把自己减去113 ans=max(sum-1,ans);114 }115 }116 printf("Case %d: %d\n",++kase,ans);117 bool flag=true;118 for(int i=0;i<n;i++)119 {120 if(cnt[sccno[i]]==ans)121 {122 if(flag) {printf("%d",i);flag=false;}123 else printf(" %d",i);124 }125 }126 printf("\n");127 }128 return 0;129 }
HDU 3639 Hawk-and-Chicken（强连通缩点+反向建图）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。