`

poj 1094

 
阅读更多

题意:给出字母个数,和有限个有序对(a<b)求出能确定字母序列的最少的条件个数.即,从第一个条件开始,往下,当加入某一条件时,如果能够确定这个序列,则输出这个序列,如果得出矛盾则说明冲突,如果所有条件都完毕也没有结果,则输出不能确定.
思路:每读一个有序对,添加一条边,然后对其拓扑排序,如果成功,则输出序列,如果不成功,判断其是否有环,如果有环,输出冲突,如果没有定论,则读入下一个有序对.当所有有序对读完还没有结果,输出不能确定.

 

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAXN 27

int in[MAXN], temp[MAXN], topo[MAXN]; //入度,topo排序结果
bool visit[MAXN][MAXN]; //标记i, j存在i < j关系
int n, m;//字母数,边数

int toposort() //拓扑排序,三个返回值:环、继续读边(未完成)、排序完成
{
	int u, v, count;
	int num; //入度为0的字母
	bool flag;
	count = 1; //已排序字母个数
	flag = true;
	memset(topo, 0, sizeof(topo));
	int i,j;
	for( i = 1; i <= n; ++i)
		temp[i] = in[i];
	for(i = 1; i <= n; ++i)
	{
		num = 0; //这个不能写在外面,删边后度变化。。。。错了N久啊。。。
		for(j = 1; j <= n; ++j) //统计入度为0的字母个数
			if(temp[j] == 0)
			{
				u = j;
				num++;
			}
			if(num == 0) //为环
				return 0;
			if(num > 1) //多条分支,继续读边
				flag = false;
			temp[u] = -1;
			topo[count++] = u; //加入拓扑序列
			for(int j = 1; j <= n; ++j) //删边操作
				if(visit[u][j] == true)
					temp[j]--;
	}
	if(flag == false)
		return -1;
	return 1; //经过n次排序到达这里,则排序完成
}

int main()
{
	char str[5];
	int start, end;
	bool flag;
	int res; //toposort返回的结果
	while(scanf("%d%d", &n, &m) != EOF)
	{
		if(n == 0 && m == 0)
			break;
		memset(in, 0, sizeof(in));
		memset(visit, false, sizeof(visit));
		flag = true;
		for(int i = 1; i <= m; ++i)
		{
			scanf("%s", str);
			if(flag == false) //出现环或者矛盾
				continue;
			start = str[0] - 'A' + 1;
			end = str[2] - 'A' + 1;
			in[end]++;
			visit[start][end] = true;
			res = toposort(); //加一次边拓扑排序一次
			if(res == 0)
			{
				printf("Inconsistency found after %d relations.\n", i);
				flag = false;
			}
			else if(res == 1)
			{
				printf("Sorted sequence determined after %d relations: ", i);
				for(int j = 1; j <= n; ++j)
					printf("%c", topo[j] + 'A' - 1);
				printf(".\n");
				flag = false;
			}
		}
		if(flag == true)
			printf("Sorted sequence cannot be determined.\n");
	}
	return 0;
}

 

 

分享到:
评论

相关推荐

    poj1094 拓扑排序

    题目“poj1094”即是要求我们实现一个拓扑排序的解决方案。 **拓扑排序**的基本思想是:对于有向无环图G,如果存在一条从顶点u到顶点v的路径,那么在拓扑排序结果中,u一定出现在v之前。拓扑排序可以得到多个不同的...

    poj 1094代码加测试工具

    【标题】"POJ 1094代码加测试工具"是关于解决一个特定的编程问题,即在编程在线评测平台POJ上提交的编号为1094的题目。这个题目可能涉及到算法的实现以及测试工具的使用,以便对程序进行验证和调试。 【描述】"POJ ...

    POJ1094-Sorting It All Out

    【标题】"POJ1094-Sorting It All Out" 是一道来自北京大学在线判题系统POJ(Problem Set)的编程题目。这道题目主要考察的是排序算法的应用与优化,旨在提高参赛者的算法设计和实现能力。 【描述】"北大POJ1094-...

    POJ算法题目分类

    * 拓扑排序:拓扑排序是指计算图的拓扑排序的算法,如 poj1094。 * 二分图的最大匹配:二分图的最大匹配是指计算二分图的最大匹配的算法,如 poj3041、poj3020。 * 最大流的增广路算法:最大流的增广路算法是指计算...

    poj题目分类

    * 拓扑排序:例如 poj1094。 * 二分图的最大匹配:例如 poj3041、poj3020。 * 最大流的增广路算法:例如 poj1459、poj3436。 3. 数据结构: * 串:例如 poj1035、poj3080、poj1936。 * 排序:例如 poj2388、...

    poj训练计划.doc

    - 拓扑排序:适用于有向无环图,用于确定任务的执行顺序,如`poj1094`。 - 二分图的最大匹配:如匈牙利算法,用于解决二分图的匹配问题,如`poj3041, poj3020`。 - **数据结构** - 字符串处理:如KMP算法和后缀...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1094 - **解释**:拓扑排序是对有向无环图的一种排序方式,可以用来解决依赖关系的问题。 ##### (5) 匹配算法 - **例题**:poj3041, poj3020 - **解释**:匹配算法主要用于解决图中节点间的匹配问题...

    poj各种分类

    适用于有向无环图,帮助分析任务依赖关系,如poj1094所示。 #### 匹配算法 包括二分图的最大匹配和KM算法,用于解决资源分配类问题,如poj3041和poj3020。 ### 三、数据结构 #### 字符串处理 如Trie树(前缀树)...

    POJ题目简单分类(ACM)

    - **拓扑排序**:对有向无环图的排序,如poj1094。 - **二分图最大匹配**:匈牙利算法,如poj3041和poj3020,解决分配问题。 - **最大流的增广路算法**:KM算法,如poj1459和poj3436,用于寻找网络中能传输的最大...

    acm训练计划(poj的题)

    - (poj1094):适用于有向无环图(DAG)的一种排序方式,表示事件发生的顺序。 5. **网络流**: - (poj3041, poj3020):探讨如何在网络中找到最大流的问题,常用算法包括福特-福克森算法等。 6. **匹配算法**: ...

    acm新手刷题攻略之poj

    - 推荐题目:[poj1094](https://vjudge.net/problem/POJ-1094) - 最大流问题通常涉及到Ford-Fulkerson算法或者Dinic算法的应用。 4. **网络流** - 推荐题目:[poj3041](https://vjudge.net/problem/POJ-3041)、...

    ACM-POJ 算法训练指南

    3. **网络流**:Max-flow算法,用于解决最大流问题(poj1094)。 4. **拓扑排序**:解决有向无环图的排序问题(poj3041, poj3020)。 5. **匹配算法**:如KM算法,用于解决二分图的最大匹配问题(poj1459, poj3436)...

    POJ 分类题目

    - poj1094 - **应用场景**:适用于任务调度、依赖关系处理等问题。 #### 三、数据结构 **1. 字符串处理** - **定义**:字符串处理技术,包括字符串匹配算法等。 - **示例题目**: - poj1035 - poj3080 - poj...

    强大的POJ分类——各类编程简单题及其算法分类

    4. **拓扑排序**:对有向无环图(DAG)的节点进行线性排序,如POJ1094。 5. **二分图的最大匹配**:使用匈牙利算法解决,如POJ3041和3020。 6. **最大流的增广路算法**:如KM算法,求解网络中的最大流量问题,如POJ...

    ACMer需要掌握的算法讲解 (2).docx

    * 拓扑排序:POJ1094 * 串算法:POJ1035、POJ3080、POJ1936 * 哈希表和二分查找等高效查找法:POJ3349、POJ3274、POJ2151、POJ1840、POJ2002、POJ2503 * 哈夫曼树:POJ3253 * 背包问题:POJ1837、POJ1276 * DP算法:...

    ACM常用算法及其相应的练习题.docx

    * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * 最大流的增广路算法:KM算法 + poj1459, poj3436 三、数据结构 * 串:poj1035, poj3080, poj1936 * 排序:快排、归并排、堆排 + poj...

    ACMer需要掌握的算法讲解.docx

    7. 拓扑排序(poj1094) 8. 串(poj1035, poj3080, poj1936) 9. 哈希表和二分查找等高效查找法(poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503) 10. 哈夫曼树(poj3253) 二、图算法 1. 度限制最小生成...

    ACM常用算法及其相应的练习题 (2).docx

    (4) 拓扑排序:poj1094 (5) 二分图的最大匹配:匈牙利算法 (6) 最大流的增广路算法:KM算法 三、数据结构 本部分涵盖了数据结构,包括串、排序、简单并查集的应用、哈希表和二分查找等高效查找法、哈夫曼树和堆、...

    ACM算法总结大全——超有用!

    4. 拓扑排序:确定有向无环图的节点顺序,如poj1094。 5. 二分图的最大匹配:匈牙利算法解决分配问题,如poj3041、poj3020。 6. 增广路算法:KM算法用于求解最大流问题,如poj1459和poj3436。 三、数据结构 1. 串:...

Global site tag (gtag.js) - Google Analytics