algospot.com :: 질문과 답변: 2012 ACM 대전 리저널 K번이요

2012 ACM 대전 리저널 K번이요

문제 설명을 읽으면 곧 그래프에서 max antichain 구하는 문제이므로
Dilworth's theorem에 의해서 min path cover 문제로 바뀌는데요, 문제에 주어진 룰에 따라 그래프가 dag이므로 곧 이분 그래프로 바꿔서 풀리는건 맞는거같은데.. 문제는 antichain set의 원소들을 찍어내야되는데 이것을 어떻게 해결해야되나요? 일단 제가 짠 아래 소스는 패스들을 다 복원시켜서 패스마다 서로 comparable 안할 때 까지 원소들을 뒤져보도록 해놨는데 사이즈가 n=1000이라서 시간복잡도가 좀 나올거같네요..

live archive에 이제 대전 리저널 온라인 졋지가 가능해졌는데 이문제는 스페셜 졋지라 일단 K번은 제대로 졋지가 안될거같긴 하구요, 보니까 live archive에 설정된 시간 제한이 15초네요; 제 생각엔 antichain set 원소 찍어내는 작업때문에 저렇게 늘려놓은거같은데..

이거 혹시 해법이 패스 커버가 아니라 아예 다른 풀이인가요? ㅜㅜ

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int T,n;
int s[1111],d[1111];
int t[1111][1111];

bool adj[1111][1111],seen[1111];
int seenR[1111],seenL[1111];

bool bpm(int u) {
    for(int v=1;v<=n;++v) if(adj[u][v]) {
        if(seen[v]) continue;
        seen[v]=1;
        if(seenR[v]==-1||bpm(seenR[v])) {
            seenR[v]=u;
            seenL[u]=v;
            return 1;
        }
    } return 0;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    cin>>T;
    while(T--) {
        memset(adj,0,sizeof(adj));
        memset(seenR,-1,sizeof(seenR));
        memset(seenL,-1,sizeof(seenL));

        cin>>n;
        for(int i=1;i<=n;++i) cin>>s[i];
        for(int i=1;i<=n;++i) cin>>d[i];
        for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) {
            int x; cin>>x;
            t[i][j]=t[j][i]=x;
        }
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
            if(i==j) continue;
            if(s[i]+d[i]+t[i][j]<=s[j]) adj[i][j]=1;
        }
        int ans=0;
        for(int i=1;i<=n;++i) {
            memset(seen,0,sizeof(seen));
            if(bpm(i)) ans++;
        } cout<<n-ans<<endl;

        vector< vector<int> > pathes;
        int idx[1111] = {0};
        for(int i=1;i<=n;++i) if(seenR[i]==-1) {
            vector<int> path; int u = i;
            do {
                path.push_back(u);
                u = seenL[u];
            } while(u != -1);
            pathes.push_back(path);
        }
        while( true ) {
            for(int i=0;i<pathes.size();++i) for(int j=0;j<pathes.size();++j) {
                if(i == j) continue;
                if(adj[pathes[i][idx[i]]][pathes[j][idx[j]]]) {
                    idx[i]++;
                    goto end;
                }
            } break;
end:;
        }
        for(int i=0;i<pathes.size();++i) {
            cout<<pathes[i][idx[i]];
            if(i != (int)pathes.size() - 1) cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

바뀐 코드

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int T,n;
int s[1111],d[1111];
int t[1111][1111];

vector<int>  adj[1111];
vector<int> radj[1111];
bool seen[1111];
bool used[1111];
int seenR[1111],seenL[1111];

bool bpm(int u) {
    for(int i=0;i<adj[u].size();++i) {
        int v = adj[u][i];
        if(!used[v]) {
            if(seen[v]) continue;
            seen[v]=1;
            if(seenR[v]==-1||bpm(seenR[v])) {
                seenR[v]=u;
                seenL[u]=v;
                return 1;
            }
        }
    } return 0;
}

int match() {
    memset(seenR,-1,sizeof(seenR));
    memset(seenL,-1,sizeof(seenL));

    int ans=0;
    for(int i=1;i<=n;++i) if(!used[i]) {
        memset(seen,0,sizeof(seen));
        if(bpm(i)) ans++;
    } return ans;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d",&T);
    while(T--) {
        memset(used,0,sizeof(used));

        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",&s[i]);
        for(int i=1;i<=n;++i) scanf("%d",&d[i]);
        for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) {
            int x; scanf("%d",&x);
            t[i][j]=t[j][i]=x;
        }
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
            if(i==j) continue;
            if(s[i]+d[i]+t[i][j]<=s[j]) 
                adj[i].push_back(j),
                radj[j].push_back(i);
        }

        int antiset = n - match(), erased = 0;
        printf("%d\n",antiset);

        while(antiset > 1) {
            for(int u=1;u<=n;++u) if(!used[u]) {
                int deg = 1; used[u] = 1;
                vector<bool> changed(adj[u].size(),0);
                vector<bool> rchanged(radj[u].size(),0);
                for(int i=0;i<adj[u].size();++i) {
                    int v = adj[u][i];
                    if(!used[v]) deg++, changed[i] = used[v] = 1;
                }
                for(int i=0;i<radj[u].size();++i) {
                    int v = radj[u][i];
                    if(!used[v]) deg++, rchanged[i] = used[v] = 1;
                }
                int mat = match();
                erased += deg, antiset--;
                if(antiset == n - erased - mat) {
                    printf("%d ",u);
                    goto next;
                }
                erased -= deg, antiset++;
                used[u] = 0;
                for(int i=0;i<adj[u].size();++i) {
                    int v = adj[u][i];
                    if(changed[i]) used[v] = 0;
                }
                for(int i=0;i<radj[u].size();++i) {
                    int v = radj[u][i];
                    if(rchanged[i]) used[v] = 0;
                }
            } next:;
        }
        for(int u=1;u<=n;++u) if(!used[u]) {
            printf("%d\n", u);
            break;
        }
        for(int i=1;i<=n;++i) 
            adj[i].clear(),
            radj[i].clear();
    }
    return 0;
}

11년 전

1개의 댓글이 있습니다.

xesmaster

생각해봤는데 하나씩 빼가면서 매칭 계속 돌려나가면서 시뮬로 찾으면 무조건 정해는 나오겠네요.. 저렇게 바뀐 코드로 해서 live archive에 제출하면 1초 안에 답은 뱉어내는데 여전히 스페셜 졎지가 안되서 WA네여.. >_<;

10년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

2012 ACM 대전 리저널 K번이요

1개의 댓글이 있습니다.