- 浏览: 202435 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
题意:给出字母个数,和有限个有序对(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;
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 841虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 842选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 870题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 986题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 970字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1446题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 1019大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1614题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2714是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1274在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 803从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2397题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 3393
2012-05-23 17:00 1259大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 994大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 1011题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2171大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1626题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1259题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 950题意:Ted今年100岁,给出n对他家族的关系:“父 ... -
poj 1656
2012-04-19 10:07 1121题目要求:一道纯的模拟题目。 直接上代码: ...
相关推荐
题目“poj1094”即是要求我们实现一个拓扑排序的解决方案。 **拓扑排序**的基本思想是:对于有向无环图G,如果存在一条从顶点u到顶点v的路径,那么在拓扑排序结果中,u一定出现在v之前。拓扑排序可以得到多个不同的...
【标题】"POJ 1094代码加测试工具"是关于解决一个特定的编程问题,即在编程在线评测平台POJ上提交的编号为1094的题目。这个题目可能涉及到算法的实现以及测试工具的使用,以便对程序进行验证和调试。 【描述】"POJ ...
【标题】"POJ1094-Sorting It All Out" 是一道来自北京大学在线判题系统POJ(Problem Set)的编程题目。这道题目主要考察的是排序算法的应用与优化,旨在提高参赛者的算法设计和实现能力。 【描述】"北大POJ1094-...
* 拓扑排序:拓扑排序是指计算图的拓扑排序的算法,如 poj1094。 * 二分图的最大匹配:二分图的最大匹配是指计算二分图的最大匹配的算法,如 poj3041、poj3020。 * 最大流的增广路算法:最大流的增广路算法是指计算...
* 拓扑排序:例如 poj1094。 * 二分图的最大匹配:例如 poj3041、poj3020。 * 最大流的增广路算法:例如 poj1459、poj3436。 3. 数据结构: * 串:例如 poj1035、poj3080、poj1936。 * 排序:例如 poj2388、...
- 拓扑排序:适用于有向无环图,用于确定任务的执行顺序,如`poj1094`。 - 二分图的最大匹配:如匈牙利算法,用于解决二分图的匹配问题,如`poj3041, poj3020`。 - **数据结构** - 字符串处理:如KMP算法和后缀...
- **例题**:poj1094 - **解释**:拓扑排序是对有向无环图的一种排序方式,可以用来解决依赖关系的问题。 ##### (5) 匹配算法 - **例题**:poj3041, poj3020 - **解释**:匹配算法主要用于解决图中节点间的匹配问题...
适用于有向无环图,帮助分析任务依赖关系,如poj1094所示。 #### 匹配算法 包括二分图的最大匹配和KM算法,用于解决资源分配类问题,如poj3041和poj3020。 ### 三、数据结构 #### 字符串处理 如Trie树(前缀树)...
- **拓扑排序**:对有向无环图的排序,如poj1094。 - **二分图最大匹配**:匈牙利算法,如poj3041和poj3020,解决分配问题。 - **最大流的增广路算法**:KM算法,如poj1459和poj3436,用于寻找网络中能传输的最大...
- (poj1094):适用于有向无环图(DAG)的一种排序方式,表示事件发生的顺序。 5. **网络流**: - (poj3041, poj3020):探讨如何在网络中找到最大流的问题,常用算法包括福特-福克森算法等。 6. **匹配算法**: ...
- 推荐题目:[poj1094](https://vjudge.net/problem/POJ-1094) - 最大流问题通常涉及到Ford-Fulkerson算法或者Dinic算法的应用。 4. **网络流** - 推荐题目:[poj3041](https://vjudge.net/problem/POJ-3041)、...
3. **网络流**:Max-flow算法,用于解决最大流问题(poj1094)。 4. **拓扑排序**:解决有向无环图的排序问题(poj3041, poj3020)。 5. **匹配算法**:如KM算法,用于解决二分图的最大匹配问题(poj1459, poj3436)...
- poj1094 - **应用场景**:适用于任务调度、依赖关系处理等问题。 #### 三、数据结构 **1. 字符串处理** - **定义**:字符串处理技术,包括字符串匹配算法等。 - **示例题目**: - poj1035 - poj3080 - poj...
4. **拓扑排序**:对有向无环图(DAG)的节点进行线性排序,如POJ1094。 5. **二分图的最大匹配**:使用匈牙利算法解决,如POJ3041和3020。 6. **最大流的增广路算法**:如KM算法,求解网络中的最大流量问题,如POJ...
* 拓扑排序:POJ1094 * 串算法:POJ1035、POJ3080、POJ1936 * 哈希表和二分查找等高效查找法:POJ3349、POJ3274、POJ2151、POJ1840、POJ2002、POJ2503 * 哈夫曼树:POJ3253 * 背包问题:POJ1837、POJ1276 * DP算法:...
* 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * 最大流的增广路算法:KM算法 + poj1459, poj3436 三、数据结构 * 串:poj1035, poj3080, poj1936 * 排序:快排、归并排、堆排 + poj...
7. 拓扑排序(poj1094) 8. 串(poj1035, poj3080, poj1936) 9. 哈希表和二分查找等高效查找法(poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503) 10. 哈夫曼树(poj3253) 二、图算法 1. 度限制最小生成...
(4) 拓扑排序:poj1094 (5) 二分图的最大匹配:匈牙利算法 (6) 最大流的增广路算法:KM算法 三、数据结构 本部分涵盖了数据结构,包括串、排序、简单并查集的应用、哈希表和二分查找等高效查找法、哈夫曼树和堆、...
4. 拓扑排序:确定有向无环图的节点顺序,如poj1094。 5. 二分图的最大匹配:匈牙利算法解决分配问题,如poj3041、poj3020。 6. 增广路算法:KM算法用于求解最大流问题,如poj1459和poj3436。 三、数据结构 1. 串:...