顺序查找 forms boost solr nhibernate fonts model rxjs bitmap x86 textview jquery多个元素绑定同一个事件 jq获取元素 linux自动获取ip java多行注释 hadoop创建文件夹 pip环境变量 matlab自然对数 plsql连接mysql yml文件注释 kubernetes集群 python运行环境 python中的def 怎么安装java环境 java实现队列 java中的集合 java重命名 tabletpc 高效能人士的七个习惯pdf redis入门指南 系统维护工具 cubase下载 medcalc php取整 c4d挤压 发射爱心的图片 fastcgi sql2008r2 电脑上传速度慢 mysql中文乱码
当前位置: 首页 > 学习教程  > 编程语言

纪中周末训练 2020.09.19【NOIP提高B组】模拟 T3:【Usaco2009 gold】头晕的奶牛

2020/9/19 16:03:40 文章标签:

【Usaco2009 gold】头晕的奶牛

Description

奶牛们发现,在农场里面赛跑是很有趣的一件事。可是她们一旦在农场里面不断地转圈,就会变得头晕目眩。众所周知,眩晕的奶牛是无法产奶的。于是,农夫约翰想要把他农场里面的双向道路全部改为单向道路,使得他的农场里面一个“圈”都没有,以避免他的奶牛们被搞得晕头转向。如果奶牛可以经过若干条道路回到起点,那么这些道路就称为一个“圈”。
  农场有N(1 <= N <= 100000)片草地,编号为1到N。这些草地由M1(1 <= M1 <= 100000)条单向道路和M2(1 <= M2 <= 100000)条双向道路连接起来。任何一条道路都不会把一片草地和这篇草地本身连接起来。但是,任意两片草地之间都可能有多条道路连接。不保证任意两片草地之间都有路径相连。
  你的任务是给所有的双向道路设定一个方向,使得整个农场(只剩下单向道路)最后一个圈都没有。也就是说,不存在一个单向道路序列的终点和起点重合。数据保证一开始就有的单向道路中,一个圈都没有。而且一开始就有的单向道路不能改变。
  单向道路的起点是草地A_i(1 <= A_i <= N),终点是草地B_i(1 <= B_i <= N)。双向道路连接草地X_i(1 <= X_i <= N)和Y_i(1 <= Y_i <= N)。
  考虑下面这个样例:
 在这里插入图片描述
  草地1和3,2和3,2和4之间的道路是双向的。还有单向道路连接草地1和2,4和3。一种给双向道路定义方向的方法是,让三条双向道路的方向分别是1到3,2到3,3到4:
在这里插入图片描述

Input

第1行: 三个由空格隔开的正数: N, M1和M2
第2到1+M1行: 第i+1行表示第i条单向道路,包含两个由空格隔开的整数: A_i和B_i
第2+M1到第1+M1+M2行: 第i+M1+1行表示第i条单向道路,包含两个由空格隔开的整数X_i和Y_i

Output

第1到M2行: 第i行应该包含两个由空格隔开的整数: 根据你给第i条双向道路定义的的方向,可能是X_i, Y_i,也可能是Y_i, X_i。这些双向道路必须按照输入的顺序输出。如果无解,在单独的一行内输出"-1"。

Sample Input

4 2 3
1 2
4 3
1 3
4 2
3 2

Sample Output

1 3
2 4
2 3

反思&题解

比赛思路: 乱建了一个图瞎搞了差不多2h,最后放弃
正解思路: 看到有向无环图,很显然想到拓扑排序(别问我为什么,其他大佬说的),将固定的有向边连好之后选入度为零的点一次做拓扑排序,之后对于x和y两个点选取拓扑序小的点作为起点就行了(玄学~~)
反思: 对于各种算法的理解还是要更深一点

CODE

#include<bits/stdc++.h>
using namespace std;
struct arr
{
	int next,to;
}edge[500005];
int cnt,n,m1,rudu[100005],head[100005],m2,num[100005],tot;
queue<int>q;
void add(int u,int v)
{
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
int main()
{
	freopen("dizzy.in","r",stdin);
	freopen("dizzy.out","w",stdout); 
	scanf("%d%d%d",&n,&m1,&m2);
	int i;
	for (i=1;i<=m1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		rudu[y]++;
		add(x,y);
	}
	tot=0;
	for (i=1;i<=n;i++)
		if (!rudu[i]) q.push(i);
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		num[u]=++tot;
		for (i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].to;
			if (!(--rudu[v])) q.push(v);
		} 
	}
	for (i=1;i<=m2;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if (num[x]<num[y]) printf("%d %d\n",x,y);
		else printf("%d %d\n",y,x);
	}
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_200342.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?