本文主要是介绍Hust oj 1631 技能修炼(拓扑排序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
技能修炼 |
Time Limit: 1000 MS | Memory Limit: 32768 K | Total Submit: 39(25 users) | Total Accepted: 26(24 users) | Rating: | Special Judge: No | |
Description |
寒假第三次周赛强势袭来,首先祝愿大能依靠自己所学的取得一个好成绩。学习之余,我们在这里说一个有关游戏的问题,你来解决一下。一般的游戏中人物技能在修炼时有个特点,就是后面的技能一般都要修炼了前面的某些个才可以修炼。比如10级有一个技能火弹术,20级有一个火焰术,那么此时假如你没修炼10级的火弹,你就不能直接修20级的火焰术,就是这样的道理。现在的问题是,给定一些个技能间的依赖关系,你来写程序来判断该以什么样的顺序来修炼这些技能。为了简化问题,我们用数代表不同的技能,一个数代表一种技能,输入形式N1 N2则代表N1是N2的前置技能。 |
Input |
本题有多组测试数据,每组中第一行为两个数N(1 <= N <= 500)和M(1 <= M <= N*(N-1)/2),其中N表示技能总数,接下来有M行。每行是代表两个技能的数字N1和N2,表示N1是N2的前置技能。 |
Output |
对每组测试数据,输出确定下来的技能修炼顺序,要求对于输入的每组数据,输出一行,一行中各技能之间以一个空格间隔(行尾不该有空格而是换行符)。 注意,对于排序的结果可能不是唯一的,这时要求先输出代表技能的数较小的。 |
Sample Input |
4 3 1 2 2 3 4 3 |
Sample Output |
1 2 4 3 |
Hint |
对于上面的样例中2和4都是3的前置技能,但是数字2较小,因此先输出2。 模板题
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn = 505;
int a[maxn][maxn];
int degree[maxn]; //记录每个节点所拥有的度的数组
int output[maxn]; //输出数组
int n,m;
int x,y;
int cnt;void Toposort()
{while(true){int pos = 1; //初始化位置为1while(degree[pos]) //如果度不等于0,继续循环{pos++;if(degree[pos] == 0 || pos >n)//如果度为0或者超过排序数组长度的话终止break;}degree[pos] = -1; //将找到的度为0的节点的度标记为已经使用过output[cnt++] = pos; //将节点放入输出数组if(cnt == n) //如果输出数组元素个数和排序数组元素个数相等终止循环break;for(int i=1;i<=n;i++){if(a[pos][i] > 0){degree[i]--; //将找到的节点的相邻节点度数减一a[pos][i] = -1;//将找到的节点和相邻节点之间的边删去}}}
}
int main()
{while(~scanf("%d%d",&n,&m)){memset(a,0,sizeof(a));memset(degree,0,sizeof(degree)); //数组初始化为0for(int i=0;i<m;i++){scanf("%d%d",&x,&y);if(a[x][y] == 0) //防止有重边{degree[y]++; //因为是x在y的前面,所以y的度加一a[x][y]++;}}cnt = 0;Toposort();for(int i=0;i<n;i++){printf("%d",output[i]);if(i != n-1)printf(" ");}printf("\n");}return 0;
}
|
这篇关于Hust oj 1631 技能修炼(拓扑排序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!