2012 ACM 대전 리저널 K번이요

  • xesmaster
    xesmaster

    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
    xesmaster

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


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