HDU 3639 Hawk-and-Chicken(强连通分量+缩点)
http://acm.hdu.edu.cn/showproblem.php?pid=3639
题意:给你一个有向图,如果从u点能到达v点,那么说u是v的粉丝,现在要你按序输出那些粉丝数目最多的点编号.
分析:
假设该图是一个强连通图,那么任一点都有n-1个粉丝(即n-1个点能到达它).所以我们把该图缩点变成一个新的DAG图.
结论:原图中具有最多粉丝的点一定在新图的那些出度为0的点所代表的分量中.
证明:假设u节点粉丝最多且它所属的分量出度不为0,那么u节点一定是某个节点v的粉丝,所以v的粉丝必然包含了u的所有粉丝加上u本身.所以v的粉丝必然多余u.由此矛盾.
下面的问题是如何找新DAG图的每个节点(所代表分量中的原节点)的最大粉丝数? 该粉丝数=本连通分量的点数-1+本连通分量能通过ß这种边逆向走到的所有分量的点数和. 所以我们直接建立缩点树的逆图DAG即可,如果u->v表示u分量将获得v分量的所有节点作为粉丝.所以我们只需要对那几个入度为0的点做DFS即可.
每次DFS到一个新节点,该点所代表的分量节点数就都加到sum上去,表示新加了很多粉丝.最后找最大粉丝值的分量点输出即可.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn= 5000+10;
int n,m;
vector<int> G[maxn], G2[maxn];
stack<int> S;
int dfs_clock, scc_cnt;
int pre[maxn],sccno[maxn],low[maxn];
int num[maxn];//表每个强连通分量各含多少点
int in[maxn];//新DAG的逆图中点的入度
int fan[maxn];//表新DAG中第i个点(分量)有多少粉丝
void dfs(int u)
{
pre[u]=low[u]=++dfs_clock;
S.push(u);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(!pre[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!sccno[v])
low[u]=min(low[u],pre[v]);
}
if(low[u]==pre[u])
{
scc_cnt++;
num[scc_cnt]=0;
while(true)
{
int x=S.top(); S.pop();
sccno[x]=scc_cnt;
num[scc_cnt]++;
if(x==u) break;
}
}
}
void find_scc(int n)
{
dfs_clock=scc_cnt=0;
memset(pre,0,sizeof(pre));
memset(sccno,0,sizeof(sccno));
for(int i=0;i<n;i++)
if(!pre[i]) dfs(i);
}
bool vis[maxn];
int dfs2(int u)
{
vis[u]=true;
int sum=0;
for(int i=0;i<G2[u].size();i++)
{
int v=G2[u][i];
if(!vis[v]) sum+=num[v]+dfs2(v); //WA-> vis[i] num[i] dfs2(i)
}
return sum;
}
int main()
{
int T; scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) G[i].clear();
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
}
find_scc(n);
memset(in,0,sizeof(in));
for(int i=1;i<=scc_cnt;i++) G2[i].clear();
for(int u=0;u<n;u++)
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
int x=sccno[u], y=sccno[v];
if(x!=y)
{
in[x]++;
G2[y].push_back(x);//建立DAG的逆图
}
}
memset(fan,0,sizeof(fan));
int max_f=-1;
for(int i=1;i<=scc_cnt;i++)
if(!in[i])
{
memset(vis,0,sizeof(vis)); //WA-> vis数组只在外面初始化1次
fan[i] = num[i]-1+dfs2(i);
max_f=max(fan[i],max_f);
}
bool win[maxn];
memset(win,0,sizeof(win));
for(int i=0;i<n;i++)
if(fan[sccno[i]]==max_f) win[i]=true;
printf("Case %d: %d\n",kase,max_f);
bool first=true;
for(int i=0;i<n;i++)if(win[i])
{
if(first) printf("%d",i), first=false;
else printf(" %d",i);
}
puts("");
}
return 0;
}
分享到:
相关推荐
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU 里面的2000~2099道题目的源码。谢谢支持
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
杭电ACM2000-2099题的解题报告
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
求一个有向图n个点 m 条边,是否是强连通分量,如果是输出Yes, 不是输出No. 数据范围 n < 10000, m < 100000 思路: Tarjan模板题 补习: AC code: /* Tarjan求有向图的强连通分量, */ #include #...
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
示例 2:输入:n = 10输出:37解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
从第 1 秒开始,每 一秒最 开始 时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):如果还没收到任何回复信息,那么该服务器