查看: 843|回復: 0

[POJ] 3041 - Asteroids

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2015-3-9 22:33:19 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 domen111 於 2015-3-9 22:36 編輯

    http://poj.org/problem?id=3041

    這題和TOJ201很類似,解法是轉換成二分圖匹配,把行星轉換成匹配邊,把每個射擊(行or列)轉換成點,不過這篇重點並不在怎麼轉換所以就不多做說明了。

    如果這題直接用這篇(tioj 1376)的解法會RE掉,RE code: http://ideone.com/dEm0eN,但tioj那題並不會,大概是因為點數太少了(只有10個點)。

    所以重點就是必須要檢查某個點是否走過,不能重複走已經走過的點,也就是code裡面的used陣列

    至於RE的原因呢? 我目前覺得應該是遞迴過深,以下是一組Sylveon提供會造成同一點重複find的測資


    AC code:
    [C++] 純文本查看 復制代碼
    #include<iostream>
    #include<vector>
    #include<cstring>
    #define endl '\n'
    using namespace std;
    typedef long long ll;
    int n,k;
    vector<int> g[510];
    int match[510]={};
    bool used[510];
    bool find(int i)
    {
            used[i]=true;
            for(int j=0;j<g[i].size();j++)
            {
                    int &m=match[g[i][j]];
                    if(m==0 || !used[m] && find(m))
                    {
                            m=i;
                            return true;
                    }
            }
            return false;
    }
    int main()
    {
            ios::sync_with_stdio(0);
            cin.tie(0);
            
            cin>>n>>k;
            for(int i=0;i<k;i++)
            {
                    int a,b;
                    cin>>a>>b;
                    g[a].push_back(b);
            }
            int ans=0;
            for(int i=1;i<=n;i++)
            {
                    memset(used,0,sizeof used);
                    if(find(i))
                            ans++;
            }
            cout<<ans<<endl;
    }
    

    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表