[ZJ][DLX][最少重覆覆蓋] b199. D. 郵輪＠Morris' Blog

2012-10-23 20:29:52| 人氣1,025| 回應3 | 上一篇 | 下一篇

[ZJ][DLX][最少重覆覆蓋] b199. D. 郵輪

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

內容：

豪華郵輪 Makoto 號是Overflow 社計劃中的新型海上渡假設施。這艘船將會有一千個以上的客房，各種娛樂設施、餐飲設施，目標是成為全亞洲最大的郵輪公司。
在設計時，Overflow 社的設計師們將Makoto 號的內部構造簡化成由房間和走廊組成的一張圖，每條走廊恰好連到兩個房間。用比較抽象的方式安排房間和走廊的配置。他們做了很多種不同的設計，但都有一個共同的問題：服務員的準備室該放在哪些地方？
對郵輪來說，服務品質是非常重要的一件事。為了達到一定的服務品質，上級對服務員準備室的地點有一些要求，
(1) 要用最快的速度回應客人，所以每條走廊的兩端至少要有一邊是服務員的準備室。
(2) 每個房間至少要和一間準備室相鄰(相鄰的定義是有一條走廊連接這個房間)，理由同上。
(3) 為了不讓設備太過分散，當作服務員準備室的房間不能超過八個。
如果一張設計圖中能夠找到一些房間滿足這三項條件，則這樣的設計圖是好的設計圖。
Overflow 社的設計師們想請你寫個程式，讓他們能從大量的設計圖中快速挑出好的設計圖。

輸入說明：

輸入檔有多筆測試資料。每筆的第一行是兩個數字 n, m(1 <= n <= 1000, 0 <= m <=1000000 ，分別代表房間數目和走廊數目。
接下來 m 行，每行兩個數字x, y，代表編號x 的房間和編號y 的房間有走廊相連。
房間編號從 0 到n-1。
n=m=0 表示input 結束。

輸出說明：

對每個測試資料，如果設計圖是好的，請輸出"Nice boat."(不含引號)。
如果是不好的，請輸出"Makoto should die!"

範例輸入：

範例輸出：

Nice boat.
Nice boat.
Makoto should die!

提示：

出處：

2008 NPSC 高中組初賽

使用 dancing links 的最少重覆覆蓋版本，最後記得可以在計算 H() 的地方也可以剪枝。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxv 100000
#include <vector>
using namespace std;
struct DacingLinks {
    int left, right;
    int up, down;
    int ch;
}DL[3000000];
int s[1005001], o[1005001], head, size, Ans;
void Remove(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = DL[i].left;
        DL[DL[i].left].right = DL[i].right;
        s[DL[i].ch]--;
    }
}
void Resume(int c) {
    static int i;
    for(i = DL[c].down; i != c; i = DL[i].down) {
        DL[DL[i].right].left = i;
        DL[DL[i].left].right = i;
        s[DL[i].ch]++;
    }
}
int used[1005001] = {};
int H() {
    static int c, ret, i, j, time = 0;
    for(c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
        if(used[c] != time) {
            ret ++, used[c] = time;
            if(ret > 8)    return ret;
            for(i = DL[c].down; i != c; i = DL[i].down)
                for(j = DL[i].right; j != i; j = DL[j].right)
                    used[DL[j].ch] = time;
        }
    }
    return ret;
}
void DFS(int k) {
    if(k + H() > 8 || Ans <= 8)    return;
    if(DL[head].right == head) {
        if(k < Ans)    Ans = k;
        return;
    }
    int t = Maxv, c, i, j;
    for(i = DL[head].right; i != head; i = DL[i].right) {
        if(s[i] < t) {
            t = s[i], c = i;
        }
    }
    for(i = DL[c].down; i != c; i = DL[i].down) {
        Remove(i);
        for(j = DL[i].right; j != i; j = DL[j].right)    Remove(j);
        DFS(k+1);
        for(j = DL[i].left; j != i; j = DL[j].left)        Resume(j);
        Resume(i);
    }
}
int new_node(int up, int down, int left, int right) {
    DL[size].up = up, DL[size].down = down;
    DL[size].left = left, DL[size].right = right;
    DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
    return size++;
}
void new_row(int n, int Row[]) {
    int a, r, row = -1, k;
    for(a = 0; a < n; a++) {
        r = Row[a];
        DL[size].ch = r, s[r]++;
        if(row == -1) {
            row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
        }else {
            k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
        }
    }
}
void init(int m) {
    size = 0;
    head = new_node(0, 0, 0, 0);
    int i;
    for(i = 1; i <= m; i++) {
        new_node(i, i, DL[head].left, head);
        DL[i].ch = i, s[i] = 0;
    }
}
struct Pt {
    int x, e;
};
int main() {
    int n, m, x, y, i;
    while(scanf("%d %d", &n, &m) == 2 && n) {
        vector<Pt> g[n+1];
        Pt tmp;
        for(i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x++, y++;
            tmp.x = y, tmp.e = i+n+1;
            g[x].push_back(tmp);
            tmp.x = x;
            g[y].push_back(tmp);
        }
        init(n+m);
        int Row[10005], nt;
        for(i = 1; i <= n; i++) {
            used[i] = 0;
            nt = 1, Row[0] = i;
            for(vector<Pt>::iterator it = g[i].begin();
                it != g[i].end(); it++)
                Row[nt++] = it->x, Row[nt++] = it->e;
            new_row(nt, Row);
        }
        Ans = Maxv;
        DFS(0);
        if(Ans <= 8)
            puts("Nice boat.");
        else
            puts("Makoto should die!");
    }
    return 0;
}

我要檢舉

#DLX#最少重覆覆蓋#b199#D. 郵輪

台長： Morris

您可能對以下文章有興趣

[ZJ] a361. A. 賓果遊戲

b238. A. 腹黑、傲嬌

b255. D. 跑跑卡丁車

d589. B. 水之國的奇幻冒險

人氣(1,025) | 回應(3)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:[NPSC][方格法] b256. E. 大風吹
此分類上一篇:[ZJ] a361. A. 賓果遊戲

回應(3)