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

题目地址: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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » HDU 3639 Hawk-and-Chicken (强连通分量+树形DP)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡