登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

poj1094 Sorting It All Out 拓扑排序  

2008-11-16 20:33:33|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
这个方法很简单,思路是这样的,对于每次输入一个关系后,我们就对输入进行一次拓扑排序,拓扑排序的结果有三种情况。
结果确定的两种情况:
第一种,如果排序后,序列中的节点数目<n,说明出现了环,因此应该直接输出,一旦结果确定,以后的输入就不用判断了。
第二种,如果排序后,节点数目刚好等于n,并且序列里相邻的节点已经明确出现了<,关系,说明大小关系已经确定了
还有一种,只能说明到目前为止知道的信息不足以判断,还需要继续看以后的输入才行
第三种情况,即排序后,节点数目刚好等于n,但是序列里相邻的节点还未明确出现<关系

代码如下:
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 26
#define debug
#undef debug
using namespace std;
bool top_sort(int G[MAX_N][MAX_N],int n ,int relation_no){
    bool is_add[MAX_N];
    int temp_g[MAX_N][MAX_N];
    vector <int> sorted_res;
    memset(is_add,false,sizeof(is_add));
    for(int i = 0 ; i < MAX_N ; i++){
        for(int j = 0 ; j < MAX_N ; j++)
                temp_g[i][j] = G[i][j];
    }

    #ifdef debug
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++)
                printf("%d ",temp_g[i][j]);
        printf("\n");
    }

    #endif

    while(true){
        int next_add = -1;
        for(int i = 0 ; i < n ; i++){
                if(is_add[i]) continue;
                bool can_be_add = true;
                for(int j = 0 ; j < n ; j++){
                    can_be_add = can_be_add && (temp_g[j][i] == 0);           
                }
                if(can_be_add){
                    is_add[i] = true;           
                    next_add = i;  
                    #ifdef debug
                    printf("%d ",i);
                    #endif     
                    break;  
                }              

        }
        if(next_add < 0) break;
        sorted_res.push_back(next_add);
        for(int j = 0 ; j < n ; j++){
                temp_g[next_add][j] = 0;
        }

    }
    if(sorted_res.size() < n){
        printf("Inconsistency found after %d relations.\n",relation_no);
        return true;
    }
    else{
        bool is_determined = true;
        for(int i = 1 ; i < sorted_res.size() ; i++){
                is_determined = is_determined&&G[sorted_res[i-1]][sorted_res[i]];//attention please we should use G instead of temp_g
        }
        if(is_determined){
                printf("Sorted sequence determined after %d relations: ",relation_no);
                for(int i = 0 ; i < sorted_res.size() ; i++){
                       printf("%c",sorted_res[i]+'A');        
                }
               
                printf(".\n");
                return true;
        }
        else{
                return false;
        }
    }

}
int main()
{  
    int n,m;
    while(scanf("%d%d",&n,&m) && !(n==0 && m==0)){
        char temp[MAX_N];
        int g[MAX_N][MAX_N];
        for(int i = 0 ; i < MAX_N ; i++){
        for(int j = 0 ; j < MAX_N ; j++)
                g[i][j] = 0;
        }
        bool is_determined = false;
        for(int i = 0 ; i < m ; i++){
                scanf("%s",temp);
                g[temp[0]-'A'][temp[2]-'A'] = 1;
                if(!is_determined){
                    is_determined = top_sort(g,n,i+1);           
                }
               
        }
        if(!is_determined)
                printf("Sorted sequence cannot be determined.\n");
    }
 
  return 0;

}
  评论这张
 
阅读(1561)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018