【日常学习】【拓扑排序】家谱树&FZU1483 Sicily1424 奖金题解

我不是女神ヾ 2022-08-04 18:27 237阅读 0赞

拓扑排序的定义 简单来说就是给你一个图写出一个序列 图中如果a通向b 那么序列中A必须排在B前面

拓扑排序可能有很多结果 必须是有向无环图 可以利用拓扑排序来判定环的存在 当然也可以用神奇的SPFA 但是拓扑排序时间复杂度很低 只有O（V+E）

基本实现思路是 每次取出入度为0的点 然后删除与它相连的边 直到没有边  如果还有边但是找不到入度为0的点 说明有环

学习这个算法联系了两道题目 很经典很单纯 但是一般没有OJ有评测 奖金这道题目在福州大学OJ和中山大学萌萌哒Sicily上找到了评测（为什么要叫西西里呢？）

先放题目：

家谱树

【题目描述】  
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。  
给出每个人的孩子的信息。  
输入一个序列，使得每个人的后辈都比那个人后列出。  
  
  
【输入】  
第一行一个整数（1<=N<=100），表示家族的人数。  
接下来N行，第I行表示第I个人的儿子。  
每行最后是0表示描述完毕。  
  
  
【输出】  
输出一个序列，使得每个人的后辈都比那个人后列出。  
如果有多解输出任意一解。  
  
  
【输入样例】  
5  
0  
4 5 1 0  
1 0  
5 3  
0  
3 0  
  
  
【输出样例】  
2 4 5 3 1

这道题目显然只需要一次拓扑排序 输出任意一个序列就可以了 不要求输出结果而是序列 因此要在过程中数组保存出队的元素 另外这道题目没有环

放代码：

普通循环的代码

//一本通 拓扑排序练习 家谱树
    //拓扑一次 输出路径 不判环 
    //copyright by ametake
    #include
       
        
    #include
        
         
    using namespace std;
    
    int n,m=0;//m是当前已经输出的点的个数 
    int r[101]={0},c[101]={0},a[101][101]={0};//a数组表示第i个数的第某个出度是谁 
    int ans[101]={0};
    
    int main()
    {
    	freopen("1.txt","r",stdin);
    	scanf("%d",&n);
    	int j;
    	for (int i=1;i<=n;i++)
    	{
    		scanf("%d",&j);
    		while (j)
    		{
    			r[j]++;
    			c[i]++;
    			a[i][c[i]]=j;
    			scanf("%d",&j);
    		}
        }
    	int t=0;
    	for (int i=1;i<=n;i++)
    	{
    		if (!r[i]) ans[++t]=i;
    	}
    	while (m!=n)
    	{
    		j=ans[t];
    		printf("%d ",j);
    		t--;
    		m++;
    		for (int i=1;i<=c[j];i++)
    		{
    			r[a[j][i]]--;
    			if (!r[a[j][i]]) {t++;ans[t]=a[j][i];}
    		}
    	}
    	return 0;
    }

、

用了STL队列的代码 更加方便易懂

//拓扑排序 家谱树 队列版 
    //拓扑一次 输出路径 不判环 
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    int n; 
    int r[101]={0},c[101]={0},a[101][101]={0};//a数组表示第i个数的第某个出度是谁 
    queue
          
            ans;
    
    int main()
    {
    	freopen("1.txt","r",stdin);
    	scanf("%d",&n);
    	int j;
    	for (int i=1;i<=n;i++)
    	{
    		scanf("%d",&j);
    		while (j)
    		{
    			r[j]++;
    			c[i]++;
    			a[i][c[i]]=j;
    			scanf("%d",&j);
    		}
        }
    	int t=0;
    	for (int i=1;i<=n;i++)
    	{
    		if (!r[i]) ans.push(i);
    	}
    	while (!ans.empty())
    	{
    		j=ans.front();
    		printf("%d ",j);
    		ans.pop();
    		for (int i=1;i<=c[j];i++)
    		{
    			r[a[j][i]]--;
    			if (!r[a[j][i]]) ans.push(a[j][i]);
    		}
    	}
    	return 0;
    }

奖金

【题目描述】  
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。  
于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。  
【输入】  
第一行两个整数n,m，表示员工总数和代表数；  
以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。  
【输出】  
若无法找到合法方案，则输出“-1”；否则输出一个数表示最少总奖金。  
输入输出样例  
reward.in  
2 1  
1 2  
reward.out  
201  
【数据范围】  
80％的数据满足n<=1000，m<=2000；  
100％的数据满足n<=10000，m<=20000。

这道题目有环，要求输出结果而不是过程，因此解唯一。采用分层处理的办法，对于每一个奖金级别集中计算。代码注释说的很清楚，此处不再赘述。

这个思路参考了黄学长的代码，但是他的代码是错误的，我已经在他的博客中指正了。

但是仍有一个疑问，本代码在Sicily测得AC，福州大学WA了 所以本代码可能也有一定问题

尝试写了STL队列版 但是时间关系没有写完 而且本题queue实现有些困难 如果成功了之后补上

上代码

//FZU1483 Sicily1424 奖金 拓扑排序有环
    //first topology by myself,cheer up!
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    int n,m,x,y;
    const int maxn=10001; 
    int r[maxn]={0},c[maxn]={0},a[maxn][301]={0};
    int ans[maxn];
    int tot=0,money=0,k=0,t=0;
    
    int main()
    {
    	freopen("1.txt","r",stdin); 
    	while (scanf("%d%d",&n,&m)==2)
    	{
    		for (int i=1;i<=m;i++)
    		{
    			scanf("%d%d",&x,&y);
    			r[x]++;
    			c[y]++;
    			a[y][c[y]]=x;
    		}
    		//先考虑黄学长的实现，再自己写队列实现 
    		while (tot

`最后补充一下 几个很好的将拓扑排序的文章： http://blog.csdn.net/dm_vincent/article/details/7714519  这个讲的有点高深，有兴趣的可以看一下 http://blog.csdn.net/liwen_7/article/details/7298736 浅显地介绍了原理 http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/topological_sort.asp 太原理工的精品课演示 有助于理解 其实所有博客都不如自己理解了最好··· 努力努力向Tarjan进发！！！ ——烟敛寒林簇，画屏展；天际遥山小，黛眉浅。`