Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个烂代码。。供有需要的人参考。。

Posted by damacheng009 at 2010-08-07 15:08:52 on Problem 2530
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using std::priority_queue;
using std::vector;

struct cmp {
    bool operator() (const int &lhs, const int &rhs) {
        return lhs > rhs;
    }
};

const int COL = 20;
char map[50][20];
bool graph[26][26];
bool used[26];
int indegree[26];
int row_num;

void build_graph() {
    for(int i = 1; i < row_num; i++) {
        for(int j = 0; j < 20; j++) {
            if(map[i][j] != '.') {
                for(int k = i - 1; k >= 0; k--) {
                    if(map[k][j] != '.' && map[i][j] != map[k][j] && graph[map[i][j] - 'A'][map[k][j] - 'A'] != true) {
                        graph[map[i][j] - 'A'][map[k][j] - 'A'] = true;
                        ++indegree[map[k][j] - 'A'];
                    }
                }
            }
        }
    }
}

void topo_sort() {
    priority_queue<int, vector<int>, cmp> q;

    for(int i = 0; i < 26; i++) {
        if(used[i] == true && indegree[i] == 0) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int cur_v = q.top();
        q.pop();

        putchar(cur_v + 'A');

        for(int i = 0; i < 26; i++) {
            if(graph[cur_v][i] == true) {
                if(--indegree[i] == 0) {
                    q.push(i);
                }
            }
        }
    }

    putchar('\n');
}

int main() {
    //freopen("e:/data.txt", "r", stdin);
    char ip[21];
    while(scanf("%d", &row_num) != EOF) {
        memset(used, false, sizeof(used));
        memset(graph, false, sizeof(graph));
        memset(indegree, 0, sizeof(indegree));

        for(int i = 0; i < row_num; i++) {
            scanf("%s", ip);
            for(int j = 0; j < 20; j++) {
                map[i][j] = ip[j];
                used[ip[j] - 'A'] = true;
            }
        }

        build_graph();
        topo_sort();
    }

    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator