24h購物| | PChome| 登入
2012-10-27 08:11:35| 人氣511| 回應0 | 上一篇 | 下一篇

[ZJ][拓樸排序] a552. 模型

推薦 0 收藏 0 轉貼0 訂閱站台

內容 ：

你買了一組模型，其中有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;
}

我要檢舉
#a552#模型#拓樸排序
台長： Morris

您可能對以下文章有興趣

人氣(511) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][掃描線] a570. 場地租借
此分類上一篇:[ZJ][dp] a564. ITSA201205 P4 Group without direct leaders

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文