HDU 3639 Hawk-and-Chicken （强连通分量+树形DP）
来源：程序员人生 发布时间：2015-03-20 08:58:02 阅读次数：2236次
题目地址：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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
