洛谷P2017 [USACO09DEC]晕牛Dizzy Cows

昨天做的这个题,记录一下。

洛谷P2017 [USACO09DEC]晕牛Dizzy Cows

题目描述

The cows have taken to racing each other around the farm but they get very dizzy when running in circles, and everyone knows that dizzy cows don’t produce any milk. Farmer John wants to convert all of the two-way cow paths in the farm to one-way paths in order to eliminate any ‘cycles’ and prevent the cows from getting dizzy. A ‘cycle’ enables a cow to traverse one or more cow paths and arrive back at her starting point, thus completing a loop or circle.

The farm comprises N pastures (1<=N<=100,0001 <= N <= 100,000) conveniently numbered 1…N. M1 (1<=M1<=100,0001 <= M1 <= 100,000) one-way cow paths and M2 two-way cow paths (1<=M2<=100,0001 <= M2 <= 100,000) connect the pastures. No path directly connects a pasture to itself, although multiple paths might connect two different pastures. A cow may or may not be able to travel between any two given pastures by following a sequence of cow paths.

Your job is to assign a direction to the two-way cow paths such that the entire farm (ultimately with only one-way paths) has no cycles. That is, there should be no sequence of one-way cow paths which leads back to its starting position. The existing one-way cow paths do not form a cycle and should be left as they are.

One-way cow paths run from pasture AiA_i (1<=Ai<=N1 <= A_i <= N) to pasture BiB_i (1<=Bi<=N1 <= B_i <= N). Two-way cow paths connect pastures XiX_i (1<=Xi<=N1 <= X_i <= N) and YiY_i (1<=Yi<=N1 <= Y_i <= N).

Consider this example:

1
2
3
4
5
1-->2 
| /|
| / |
|/ |
3<--4

The cow paths between pastures 1 and 3, 2 and 3, and 2 and 4 are two-way paths. One-way paths connect 1 to 2 and also 4 to 3. One valid way to convert the two-way paths into one-way paths in such a way that there are no cycles would be to direct them from 1 to 3, from 2 to 3, and from 3 to 4:

1
2
3
4
5
1-->2 
| /|
| / |
vL v
3<--4

翻译

奶牛们发现,在农场里面赛跑是很有趣的一件事.可是她们一旦在农场里面不断地转圈,就 会变得头晕目眩.众所周知,眩晕的奶牛是无法产奶的.于是,农夫约翰想要把他农场里面的双 向道路全部改为单向道路,使得他的农场里面一个圈都没有,以避免他的奶牛们被搞得晕头转 向.如果奶牛可以经过若干条道路回到起点,那么这些道路就称为一个圈.

农场有NN(1<N<1000001 < N < 100000)片草地,编号为11NN.这些草地由M1M1条单向 道路和M2M2条双向道路连接起来.任何一条道路都不会把一片草地和这篇草地本 身连接起来.但是,任意两片草地之间都可能有多条道路连接.不保证任意两片草地之间都有路 径相连.

你的任务是给所有的双向道路设定一个方向,使得整个农场(只剩下单向道路)最后一个圈都 没有.也就是说,不存在一个单向道路序列的终点和起点重合.数据保证一开始就有的单向道路 中,一个圈都没有.而且一开始就有的单向道路不能改变.

单向道路的起点是草地AiA_i,终点是草地BiB_i.双向道路连接草 地XiX_i,YiY_i

输入输出格式

输入格式:

dizzy.indizzy.in 中输入数据

第一行 33 个整数 nnp1p1p2p2,分别表示点数,有向边的数量,无向边的数量。

第二行起输入 p1p1 行,每行 22 个整数,aabb,表示 aabb 有一条有向边。

接下来输入 p2p2 行,每行 22 个整数 aabb,表示 aabb 中间有一条无向边。

输出格式:

输出到 dizzy.outdizzy.out

对于每条无向边,我们要求按输入顺序输出你定向的结果,也就是如果你输出 aa bb,那

表示你将 aabb 中间的无向边定向为 aabb

注意,也许存在很多可行的解。你只要输出其中任意一个就好。

输入输出样例

输入样例#1:

1
2
3
4
5
6
4 2 3
1 2
4 3
1 3
4 2
3 2

输出样例#1:

1
2
3
1 3
4 2
2 3

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>

const int maxn=4e7+1;

struct edge{
int to;
int next;
}map[maxn];

int n,p1,p2;
int head[maxn],cnt;
int c[maxn];
int s[maxn],q[maxn],h[maxn];
int top,tot;

void add(int x,int y);
void toposort();

int main(){
int temp_a,temp_b;
scanf("%d%d%d",&n,&p1,&p2);
for(int i=1;i<=p1;i++){
scanf("%d%d",&temp_a,&temp_b);
add(temp_a,temp_b);
c[temp_b]++;
}
toposort();
for(int i=1;i<=n;i++){
h[q[i]]=i;
}
for(int i=1;i<=p2;i++){
scanf("%d%d",&temp_a,&temp_b);
if(h[temp_a]>h[temp_b]){
printf("%d %d\n",temp_b,temp_a);
}else{
printf("%d %d\n",temp_a,temp_b);
}
}
return 0;
}

void add(int x,int y){
map[++cnt].to=y;
map[cnt].next=head[x];
head[x]=cnt;
return ;
}

void toposort(){
for(int i=1;i<=n;i++){
if(!c[i]){
s[++top]=i;
q[++tot]=i;
}
}
while(top){
int x=s[top--];
for(int i=head[x];i;i=map[i].next){
c[map[i].to]--;
if(!c[map[i].to]){
s[++top]=map[i].to;
q[++tot]=map[i].to;
}
}
}
return ;
}
文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/02/26/洛谷P2017 [USACO09DEC]晕牛Dizzy Cows题解/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论