Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴个烂代码。。供有需要的人参考。。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator