20181029NOIP模拟赛T2

2、追捕

【题目背景】

Duan2baka:“jmsyzsfq天下第一蠢!”

jmsyzsfq:“你说什么?!”

【题目描述】

于是Duan2baka开始了逃亡的旅程,而jmsyzsfq也开始追捕Duan2baka。  他们来到了一个有n个节点的有向图,迅速逃跑的Duan2baka会首先降落在有向图的某个节点T上,因为怕发出声音,他会永远静止不动。而随后跟来的jmsyzsfq会降落在图上随机一个节点S上(可以与T相同),并可以沿着图中的有向边随意走动。因为jmsyzsfq有着敏锐的嗅觉而且绝顶聪明,他一定会沿着正确的方向寻找Duan2baka。你可以认为,如果图中存在一条合法的从S到T的路径,那么jmsyzsfq一定会抓到Duan2baka——因此jmsyzsfq能否追捕到Duan2baka在他刚刚降落在图上的时候就已经确定了。现在请你帮帮jmsyzsfq,在他降落前告诉他有多大的概率能够追捕到Duan2baka,并告诉他想要追到Duan2baka他可以降落在哪些节点上。

【输入格式】

输入第一行包含三个整数n,m,opt,表示图中有n个节点,m条有向边;opt为0或1,含义见输出格式所述。

输入第2至m+1行每行两个整数u,v描述了图中一条从u到v的有向边。

输入第m+2行一个整数T表示Duan2baka降落的位置。

【输出格式】

如果输入的opt为0,只需要输出jmsyzsfq能够追捕到Duan2baka的概率。

如果输入的opt为1,输出两行,第一行输出jmsyzsfq能够追捕到Duan2baka的概率;第二行按从小到大输出想要追到Duan2baka他可以降落的节点编号,编号间用空格隔开。

对于jmsyzsfq能够追捕到Duan2baka的概率,是一个既约分数,形如“a/b”(a,b为整数),使gcd(a,b)=1,如果a=b,输出1/1。

【样例1输入】

9 10 1

1 2

2 1

2 4

6 1

9 6

6 5

5 3

3 7

3 1

1 8

1

【样例1输出】

2/3

1 2 3 5 6 9

【样例1解释】

图*9个节点,能够到达节点S=1的节点共6个:{1,2,3,5,6,9}。所以能够追捕到Duan2baka的概率为6/9=2/3。

【样例2输入】

5 7 1

1 2

1 3

1 5

2 4

4 1

4 5

5 3

1

【样例2输出】

3/5

1 2 4

【数据范围与约定】

opt=0和opt=1的数据各50%。

对于opt=0和opt=1的情况,有着完全相同的子任务:

对于10%的数据,n,m≤100。

对于另外30%的数据,n,m≤100,000。

对于另外10%的数据,保证图是一个完全图,即对于任意两个点u和v,必然有两条有向边u→v和v→u。

对于另外20%的数据,保证图是一个有向无环图,即对于任意一个点x,不存在图上一条路径从x经过其它点后回到x。

对于另外20%的数据,保证如果图上存在一条边u→v,一定存在一条边v→u。

对于100%的数据,n,m≤1,000,000,保证数据合法且不存在重边、自环。

思路:

有大佬广搜秒切

本蒟蒻表示想复杂了

我先用tarjan缩了一遍点,然后建反图

因为求可达他的点,就是求他可达的点

然后dfs扫一遍就好了

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
using namespace std;
int low[],dfn[],sta[],tot,bnt;
int top,n,m,head[],color[],opt,cnt;
int vis[],pl,bj[];
struct ljb{
int to,nxt;
}x[];
struct cb{
int from,to;
}y[];
inline void add(int from,int to)
{
bnt++;
x[bnt].to=to;
x[bnt].nxt=head[from];
head[from]=bnt;
}
void tarjan(int wz)
{
cnt++;
low[wz]=cnt;
dfn[wz]=cnt;
top++;
sta[top]=wz;
vis[wz]=;
for(rii=head[wz];i!=;i=x[i].nxt)
{
int ltt=x[i].to;
if(dfn[ltt]==)
{
tarjan(ltt);
low[wz]=min(low[wz],low[ltt]);
}
else
{
if(vis[ltt]!=)
{
low[wz]=min(low[wz],dfn[ltt]);
}
}
}
if(low[wz]==dfn[wz])
{
tot++;
while(sta[top+]!=wz)
{
color[sta[top]]=tot;
vis[sta[top]]=;
top--;
}
}
}
void dfs(int wz)
{
bj[wz]=;
for(rii=head[wz];i!=;i=x[i].nxt)
{
int ltt=x[i].to;
if(bj[ltt]==)
{
dfs(ltt);
}
}
}
int main()
{
freopen("hunt.in","r",stdin);
freopen("hunt.out","w",stdout);
scanf("%d%d%d",&n,&m,&opt);
for(rii=;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
y[i].from=from;
y[i].to=to;
add(from,to);
}
for(rii=;i<=n;i++)
{
if(dfn[i]==)
{
tarjan(i);
}
}
memset(x,,sizeof(x));
memset(head,,sizeof(head));
bnt=;
for(rii=;i<=m;i++)
{
int from=y[i].from;
int to=y[i].to;
if(color[from]!=color[to])
{
add(color[to],color[from]);
}
}
scanf("%d",&pl);
dfs(color[pl]);
int cnt=;
for(rii=;i<=n;i++)
{
if(bj[color[i]]==)
{
cnt++;
}
}
int gc=__gcd(cnt,n);
cout<<cnt/gc<<"/"<<n/gc<<endl;
if(opt==)
{
for(rii=;i<=n;i++)
{
if(bj[color[i]]==)
{
printf("%d ",i);
}
}
}
}

(其实不缩点也完全可以)

上一篇:Bootstrap入门(二十九)JS插件6:弹出框


下一篇:微信小程序picker 日期(年/月/日/时/分)选择器