2012-10-27 08:11:35Morris
[ZJ][拓樸排序] a552. 模型
內容 ：
你買了一組模型，其中有n個零件，而零件之間有先後關係，也就是在裝上零件y之前，必須先將零件x裝上才可以，說明書上包含了m種(x, y)的關係，請問你該如何依序使用零件才能將模型完成？
輸入說明
：
本題採取循環輸入，讀至EOF時結束程式。
每筆測資會先有兩個數字n和m代表n個零件和m種關係，每種關係只會出現一次，n<=100。
接下來有m行，每行有兩個數字i和j，代表必須先將i裝上後，才能將j裝上去(i->j)。
本題必定有解，即不會有循環出現(例如1->2, 2->3, 3->1)。
輸出說明
：
輸出一行數列共有n個數字，表示該依序使用哪些零件。
如果同時有多種解，請回答字典序最小的解。(有多種零件能同時選的話，要先選編號最小的)
範例輸入 ：
5 4 0 4 4 3 2 1 3 2 3 2 2 0 1 0
範例輸出 ：
0 4 3 2 1 1 2 0
提示
：
第一組範例只有唯一一種解法。
第二組雖然有1 2 0和2 1 0兩種，但要回答字典序最小的1 2 0。
出處
：
(管理：VacationClub)
第一次想嘗試用 heap 去寫，不過似乎效率沒很好久是了，就當作是複習語法吧。
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
struct info {
int nd, deg;
info(int a, int b) : nd(a), deg(b) {}
};
struct cmp {
bool operator() (info a, info b) {
if(a.deg != b.deg)
return a.deg >= b.deg;
return a.nd >= b.nd;
}
};
int main() {
int n, m, i, j;
while(scanf("%d %d", &n, &m) == 2) {
vector<int> g[n];
priority_queue<info, vector<info>, cmp> hp;
int deg[100] = {}, used[100] = {};
while(m--) {
scanf("%d %d", &i, &j);
g[i].push_back(j);
deg[j]++;
}
for(i = 0; i < n; i++) {
info e(i, deg[i]);
hp.push(e);
}
while(!hp.empty()) {
info t = hp.top();
hp.pop();
if(used[t.nd]) continue;
printf("%d ", t.nd);
used[t.nd] = 1;
for(i = 0; i < g[t.nd].size(); i++) {
if(!used[g[t.nd][i]]) {
deg[g[t.nd][i]]--;
info e(g[t.nd][i], deg[g[t.nd][i]]);
hp.push(e);
}
}
}
puts("");
}
return 0;
}
第一次想嘗試用 heap 去寫，不過似乎效率沒很好久是了，就當作是複習語法吧。
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
struct info {
int nd, deg;
info(int a, int b) : nd(a), deg(b) {}
};
struct cmp {
bool operator() (info a, info b) {
if(a.deg != b.deg)
return a.deg >= b.deg;
return a.nd >= b.nd;
}
};
int main() {
int n, m, i, j;
while(scanf("%d %d", &n, &m) == 2) {
vector<int> g[n];
priority_queue<info, vector<info>, cmp> hp;
int deg[100] = {}, used[100] = {};
while(m--) {
scanf("%d %d", &i, &j);
g[i].push_back(j);
deg[j]++;
}
for(i = 0; i < n; i++) {
info e(i, deg[i]);
hp.push(e);
}
while(!hp.empty()) {
info t = hp.top();
hp.pop();
if(used[t.nd]) continue;
printf("%d ", t.nd);
used[t.nd] = 1;
for(i = 0; i < g[t.nd].size(); i++) {
if(!used[g[t.nd][i]]) {
deg[g[t.nd][i]]--;
info e(g[t.nd][i], deg[g[t.nd][i]]);
hp.push(e);
}
}
}
puts("");
}
return 0;
}