| ||||||||||
| 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