首页 > ACM题库 > HDU-杭电 > HDU 1336 Word Index-拓扑排序-[解题报告] C++
2013
12-09

HDU 1336 Word Index-拓扑排序-[解题报告] C++

Word Index

问题描述 :

Encoding schemes are often used in situations requiring encryption or information storage/transmission economy. Here, we develop a simple encoding scheme that encodes particular types of words with five or fewer (lower case) letters as integers.
Consider the English alphabet {a,b,c,…,z}. Using this alphabet, a set of valid words are to be formed that are in a strict lexicographic order. In this set of valid words, the successive letters of a word are in a strictly ascending order; that is, later letters in a valid word are always after previous letters with respect to their positions in the alphabet list {a,b,c,…,z}. For example,abc aep gwz

are all valid three-letter words, whereas

aab are cat

are not.

For each valid word associate an integer which gives the position of the word in the alphabetized list of words. That is:

a -> 1
b -> 2
.
.
z -> 26
ab -> 27
ac -> 28
.
.
az -> 51
bc -> 52
.
.
vwxyz -> 83681

Your program is to read a series of input lines. Each input line will have a single word on it, that will be from one to five letters long. For each word read, if the word is invalid give the number 0. If the word read is valid, give the word’s position index in the above alphabetical list.

输入:

The input consists of a series of single words, one per line. The words are at least one letter long and no more that five letters. Only the lower case alphabetic {a,b,…,z} characters will be used as input. The first letter of a word will appear as the first character on an input line.The input will be terminated by end-of-file.

输出:

The output is a single integer, greater than or equal to zero (0) and less than or equal 83681. The first digit of an output value should be the first character on a line. There is one line of output for each input line.

样例输入:

z
a
cat
vwxyz

样例输出:

26
1
0
83681

题目:http://acm.hit.edu.cn/hoj/problem/view?id=1336

http://poj.org/problem?id=1094

本题联系拓扑排序。

如果给定的所有偏序关系中,能求得唯一的拓扑排序,则输出:Sorted sequence determined after xxx relations: yyy…y. 

如果有环,则输出:Inconsistency found after xxx relations.

如果有不止一个拓扑序,则输出:Sorted sequence cannot be determined.

由于需要记录下在第几个偏序关系中能得出结论,所以每读入一个偏续就需要进行一次排序判断,toposort()可以作为拓扑排序的模板。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
using namespace std;

int map[30][30];
int indegree[30];
int n,m;

queue<int> q;
queue<int> record;

//拓扑排序
int toposort()
{
    //清空队列
    while(!q.empty())
    {
        q.pop();
    }
    while(!record.empty())
    {
        record.pop();
    }
    int in[30];
    memcpy(in,indegree,sizeof(indegree));
    for(int i=0;i<n;i++)
    {
        if(in[i] == 0)
        {
            q.push(i);
        }
    }

    int flag = 0;
    while(!q.empty())
    {
        int a = q.front();
        record.push(a);
        q.pop();
        if(!q.empty())
        {
            flag = 1;
        }
        for(int i=0;i<n;i++)
        {
            if(map[a][i] == 1)
            {
                in[i]--;
                if(in[i] == 0)
                {
                    q.push(i);
                }
            }
        }
    }
    //有环路
    if(record.size()!=n)
    {
        return 0;
    }
    //不确定排序方式
    else if(flag == 1)
    {
        return 1;
    }
    return 2;//有唯一拓扑
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif

    while(scanf(" %d %d",&n,&m)!=EOF && n!=0 && m!=0)
    {
        memset(map,0,sizeof(map));
        memset(indegree,0,sizeof(indegree));

        int flag = 0;
        for(int i=0;i<m;i++)
        {
            char a,b;
            scanf(" %c<%c",&a,&b);
            if(map[b-'A'][a-'A'] == 1)
            {
                flag = 1;
                printf("Inconsistency found after %d relations.\n",i+1);
                for(int j=i+1;j<m;j++)
                {
                    scanf(" %c<%c",&a,&b);
                }
                break;
            }
            else if(map[a-'A'][b-'A'] == 0)
            {
                map[a-'A'][b-'A'] = 1;
                indegree[b -'A']++;
            }
            int res = toposort();
            if(res == 0)
            {
                flag = 1;
                printf("Inconsistency found after %d relations.\n",i+1);
                for(int j=i+1;j<m;j++)
                {
                    scanf(" %c<%c",&a,&b);
                }
                break;
            }
            else if(res == 2)
            {
                flag = 1;
                for(int j=i+1;j<m;j++)
                {
                    scanf(" %c<%c",&a,&b);
                }
                printf("Sorted sequence determined after %d relations: ",i+1);
                while(!record.empty())
                {
                    int top = record.front();
                    record.pop();
                    printf("%c",top + 'A');
                }
                printf(".\n");
                break;
            }
        }
        if(flag == 0)
        {
            printf("Sorted sequence cannot be determined.\n");
        }

    }
    return 0;
}

解题报告转自:http://blog.csdn.net/niuox/article/details/8675430


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)