infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
poj 1094 toplogical_sort
题意 给出如下的相互关系(0 0结束) 要你判断是否在某一次读入后,能够判断所给关系
是矛盾的,或者能找出唯一符合这样关系的组合,或是最终也无法确定他们的关系。

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
方法 拓扑排序
每次读入一对关后,做一次floyd, 计算传递闭包.
然后判环,其实很简单,就是看有没有点i的map[i][i]=1;
有就证明有环!如果有环就矛盾了。
如果无环再判断是否能确定关系,(注意每次都把出入度数组清零!)计算每个点的出度+入度是否=n-1;
如果所有点都有这个关系,那么唯一的关系就确定了,接下来拓扑排序就能找出这个关系.

Source Code

Problem: 1094
User: lovecanon
Memory: 208K
Time: 32MS
Language: C++
Result: Accepted

#include<stdio.h>
#include
<string.h>
#include
<stdlib.h>
int n,m,top,map[27][27],indegree[27],outdegree[27],mem[27],s[27];
char str[27],buf[10];
int floyd(){
    
int i,j,k;
    
for(k=0;k<n;k++)
        
for(i=0;i<n;i++)
            
for(j=0;j<n;j++){
                
if(map[i][k]&&map[k][j]) map[i][j]=1;
            }

    
for(i=0;i<n;i++)
        
if(map[i][i]) return 0;
    
return 1;
}
int calc(){
    
int i,j;
    memset(indegree,
0,sizeof(indegree));
    memset(outdegree,
0,sizeof(outdegree));
    
for(i=0;i<n;i++)
        
for(j=0;j<n;j++){
            
if(map[i][j]) {indegree[j]++;outdegree[i]++;}
        }
    
    
for(i=0;i<n;i++
        
if(indegree[i]+outdegree[i]!=n-1return 0;
    
return 1;
}
void toplogical_sort(){
    
int i,j=0;
    top
=0;
    
for(i=0;i<n&&top<=1;i++if(!indegree[i]) mem[++top]=i;
    memset(s,0,sizeof(s));
    while(top){
        
int cnt=mem[top--];
        s[cnt]
=1;
        str[j
++]=cnt+'A';
        
for(i=0;i<n;i++){
            
if(!s[i] && map[cnt][i]) indegree[i]--;
            
if(i!=cnt && !s[i] && indegree[i]==0) mem[++top]=i;
        }
    }
    str[j]
='\0';
}
int main(){
    
while(scanf("%d%d",&n,&m),n&&m){
        memset(map,
0,sizeof(map));
        
int i,flag1=0,flag2=0;
        
for(i=1;i<=m;i++){
            scanf(
"%s",buf);
            map[buf[
0]-'A'][buf[2]-'A']=1;
            
if(flag1 || flag2) continue;
            
else if(!floyd()) {flag1=i;continue;}
            
else if(calc()) {toplogical_sort();flag2=i;}
        }
        
if(flag1) printf("Inconsistency found after %d relations.\n",flag1);
        
else if(flag2) printf("Sorted sequence determined after %d relations: %s.\n",flag2,str);
        
else printf("Sorted sequence cannot be determined.\n");
    }
    
return 0;
}




posted on 2008-11-06 11:48 infinity 阅读(1400) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理