NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組初賽
 NPSC 2008 高中組 初賽 D.郵輪

作者 主題: NPSC 2008 高中組 初賽 D.郵輪  (閱讀 2387 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 225
    • 檢視個人資料
NPSC 2008 高中組 初賽 D.郵輪
« 於: 十一月 30, 2009, 04:03:23 pm »

NPSC 2008 高中組 初賽 D.郵輪

說明:給你由 N 個房間所組成的圖,每個邊的兩端至少要有一端是服務室,而每個房間一定要和一間服務室相連,問你是否可以把服務室的數量控制在8個以內。

解法:圖(Graph)與貪婪演算法,首先找出沒有走廊的房間,將它們全部設成服務室,接下來找與最少房間相連的房間,此房間為正常房間,將與它相連的房間全部設成服務室,接下來再找與房間相連數第二少的房間,反覆以上步驟直到所有房間都處理過。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2008 高中組初賽
// 題目 D - 郵輪
// By sagit at TCGS
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <deque>
#define MAX 1001
#define MAX_SV 8

using namespace std;

deque<int> P[MAX];      // 計錄每個房間的走廊
int R[MAX];             // 計錄該房間是否已處理過
int Num;                // 計錄房間的總數

void InitRooms(int n)   // 將房間狀態啟始化
{
    int i, j;
    Num=n;
    for (i=0; i<n; i++)
    {
        R[i]=0;
        P[i].clear();
    }
}

void Link(int a, int b) // 連接兩個房間
{
    P[a].push_back(b);
    P[b].push_back(a);
}

int Arrange()           // 安置服務室, 若超過八間則傳回 0
{
    int sv=0, i, k, p, t; // sv 計錄服務室的個數
    for (i=0; i<Num; i++)
        if (P[i].size()==0) // 沒有走廊的房間一定是服務室
        {
            R[i]=1;     // 將服務室設為已處理
            sv++;
        }
    if (sv>MAX_SV) return 0; // 服務室超過上限則傳回 0
    while (1)
    {
        for (i=0, k=-1, p=MAX; i<Num; i++) // 尋找與最少房間相鄰的未處理房間
            if ( R[i]==0 && P[i].size()<p ) k=i, p=P[i].size();
        if (k<0) return 1; // 找不到則傳回 1
        for (i=0; i<P[k].size(); i++) // 尋找與 k 相鄰的房間
        {
            t=P[k][i];  // 取得房間編號
            if (R[t]>0) continue; // 處理過的則不再處理
            R[t]=1;     // 將該房間設為已處理
            sv++;       // 與 k 相鄰的設為服務室
        }
        R[k]=2;         // 將 k 設為已處理
        if (sv>MAX_SV) return 0; // 服務室超過上限則傳回 0
    }
}

int main()
{
    freopen("pd.in", "rt", stdin);
    freopen("pd.out", "w+t", stdout);
    int n, m, x, y, i;
    while (1)
    {
        scanf("%d%d", &n, &m);
        if ( n==0 && m==0 ) break;
        InitRooms(n);
        for (i=0; i<m; i++)
        {
            scanf("%d%d", &x, &y);
            Link(x, y);
        }
        if (Arrange()) printf("Nice boat.\n");
        else printf("Makoto should die!\n");
    }
//    system("PAUSE");
    return 0;
}
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 225
    • 檢視個人資料
補充說明
« 回覆 #1 於: 十一月 30, 2009, 04:21:18 pm »

補充說明

上面的 Greedy 做法,僅能通過本次比賽的測資,不保證在所有情況下都能得到最佳解,歡迎各位提供更正確的解法。
記錄

b821213

  • 初級會員
  • **
  • 文章數: 21
    • 檢視個人資料
回覆: NPSC 2008 高中組 初賽 D.郵輪
« 回覆 #2 於: 九月 30, 2010, 07:55:47 am »

以下轉自ZJ討論區 asleepy大的發言:

是的,這是一個 NP 的問題。意思也就是說,如果告訴你哪幾間房間是準備室的話,檢查這樣有無符合限制僅需要 P 的時間。(先檢查每條邊是否至少有一的頂點是準備室,檢查的時候順便將另外一個頂點標記,然後再檢查所有的頂點是不是都有標記或是自己就是準備室, n + m)


先看簡單一點的,如果整能有一間準備室。 那麼隨便挑一個邊,這個邊的兩邊至少有一個頂點得要是準備室。那先試試看把其中一個頂點當準備室,這樣合不合法,不行的話再把另外一個頂點當準備室看看合不合法。如果兩個放法都不行,這圖鐵定無解。

那麼如果可以擺放兩間準備室呢?隨便挑兩個沒有重疊到的邊 (v1, v2), (v3, v4) ,v1 ~ v4 都不相等,分別嘗試  [v1, v3], [v1, v4], [v2, v3], [v2, v4] 當準備室,如果這四種方法都不行,那這圖肯定無法解。

不管你取出哪兩條邊,只要這兩條邊的四個頂點都不相等,就可以得出這樣的推論。

我想嘗試說明的是,如果你能找出 8 的地方讓你選擇,每個地方必須保證一定會有一個準備室,那麼當你在這 8 個地方爆搜完後發覺還是無解的時候,你就可以肯定這絕對無解。那麼可能會花 2^8 (n + m) = 256(n + m) 。

實際上做的時候到也不用這麼麻煩 :)
記錄

gkevinyen5418

  • 新手
  • *
  • 文章數: 1
    • 檢視個人資料
Re: NPSC 2008 高中組 初賽 D.郵輪
« 回覆 #3 於: 四月 05, 2014, 05:03:40 pm »

對於那些 沒有和其他點相鄰的點
直接給他一個準備室

接著 用一個變數i
從0 跑到1<<(剩餘準備室數)
對於每個i 遍歷所有的邊
如果那個邊 已經有一點 為準備室了 則跳過
(因為 如果另一點也必須是 準備室的話
 則它必定 還有其他邊 而那時便會枚舉到)
不然 便按i 的該位bit 決定要以哪一點為 準備室

想起來 就覺得會對會對的(欸
因為 如果有可能的解 就一定會被枚舉到(?
傳上去也過了~
如果有錯 也請各位大大賜教~ <(_ _)>
代碼: [選擇]
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int N, M;
vector<int> v[2000];
bool hv[2000];

struct E
{
    int a, b;
    E(){}
    E(int _a, int _b){ a =_a; b = _b; }
}e[2000000];

int room;

int main()
{
    while(1)
    {
        scanf("%d %d", &N, &M);

        if( N == 0 && M == 0 ) break;

        for(int Ni = 0; Ni < N; Ni++) v[Ni].clear();

        for(int Mi = 0; Mi < M; Mi++)
        {
            int a, b; scanf("%d %d", &a, &b);
            v[a].push_back(b); v[b].push_back(a);
            e[Mi] = E( a, b);
        }


        room = 8;

        for(int Ni = 0; Ni < N; Ni++)
            if( v[Ni].size() == 0 ) room--;

        if( room < 0 ){ puts("Makoto should die!"); goto ED; }

        for(int i = 0; i < (1<<8); i++)
        {
            int cnt = 0;

            for(int Ni = 0; Ni < N; Ni++)
                hv[Ni] = false;

            for(int Mi = 0; Mi < M; Mi++)
            {
                if( hv[ e[Mi].a] || hv[ e[Mi].b] ) continue;
                if( cnt >= room ) goto tmp;
                if( i&(1<<cnt) ) hv[ e[Mi].a] = true;
                else hv[ e[Mi].b] = true;
                cnt++;
            }

            puts("Nice boat."); goto ED;
            tmp:;
        }

        puts("Makoto should die!");
        ED:;
    }
}
« 上次編輯: 四月 05, 2014, 05:17:52 pm 由 gkevinyen5418 »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組初賽
 NPSC 2008 高中組 初賽 D.郵輪