acm 2010 대전 리저널 F번 질문입니다

  • xesmaster
    xesmaster
    #include<cstdio>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    struct edge {
        int u,v,w;
        edge() {}
        edge(int a, int b, int c) : u(a), v(b), w(c) {}
        bool operator < (const edge &rhs) const {
            return w < rhs.w;
        }
    } E[250005];
    
    int p[555],r[555];
    vector<int> set[555];
    vector<int> adj[555];
    vector<int> wht[555];
    int T,n,m;
    
    int find(int u) {
        if(u == p[u]) return u;
        else return p[u] = find(p[u]);
    }
    
    void unite(int u, int v) {
        int x = find(u), y = find(v);
        if(x == y) return;
    
        if(r[x] >= r[y]) {
            p[y] = x, r[x] += r[y];
            for(int i=0;i<set[y].size();++i) set[x].push_back(set[y][i]);
            r[y] = 0, set[y].clear();
        }
        else if(r[x] < r[y]) {
            p[x] = y, r[y] += r[x];
            for(int i=0;i<set[x].size();++i) set[y].push_back(set[x][i]);
            r[x] = 0, set[x].clear();
        }
    }
    
    bool ck(int root) {
        int mn = 1000000, mx = 0;
        for(int i=0;i<set[root].size();++i) {
            int u =set[root][i];
            for(int j=0;j<adj[u].size();++j) {
                int v = adj[u][j];
                if(root == find(v)) mn = min(mn, wht[u][j]);
                else mx = max(mx, wht[u][j]);
                if(mx >= mn) return 0;
            }
        } return 1;
    }
    
    int main() {
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif
        scanf("%d",&T);
        while(T--) {
            scanf("%d%d",&n,&m);
            for(int i=0;i<m;++i) {
                int u,v,w; scanf("%d%d%d",&u,&v,&w), u--, v--;
                E[i] = edge(u,v,w);
                adj[u].push_back(v);
                wht[u].push_back(w);
                adj[v].push_back(u);
                wht[v].push_back(w);
            } sort(E, E + m);
    
            for(int i=0;i<n;++i) p[i] = i, r[i] = 1, set[i].push_back(i);
    
            long long ans = 0;
            for(int i=m-1;i>=0;--i) {
                int x = find(E[i].u), y = find(E[i].v);
                if(x == y) continue;
                unite(x, y);
                x = find(x);
                if(ck(x)) ans += r[x];
            } printf("%lld\n",ans);
    
            for(int i=0;i<n;++i) adj[i].clear(), wht[i].clear(), set[i].clear();
        }
    }
    

    위의 소스 풀이는 유니온파인드 이용해서 그리디하게 하는 풀이인데요, 문제 정의에 n = 5000으로 정해져있는데 저 풀이가 최악의 경우 n^3풀이라 당연히 tle를 예상하고 제출했는데 매우 빠른 시간안에 억쎕이 뜨더라구요.. 좀 이상해서 n 사이즈를 500으로 잡고 재제출을 해도 런타임 에러 대신 억쎕이 뜨더군요..
    원래 대회에선 사이즈가 500이었나요? 아님 n^3이 아닌 다른 풀이가 있는건가요? 일단 live archive 온라인 졎지에서는 데이터 자체를 500으로만 만들어논거같네요;

    문제 링크:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=382&page=show_problem&problem=2849


    6년 전
4개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    대회 때 n^2으로 푼 것 같네요.


    6년 전 link
  • xesmaster
    xesmaster

    어떻게 푸셨나요 ㅠㅠ 간략하게라도 설명 부탁드려요


    6년 전 link
  • kcm1700
    kcm1700


    x님이 하신 것과 방법은 거의 같아요. 일단 인접행렬을 썼어요. unite 연산에 unite한 집합끼리 크로스로 edge를 확인해주고 값을 계산해요. 그렇게 하면 각 edge마다 최대 한번씩만 보게 되어요.


    6년 전 link
  • xesmaster
    xesmaster

    아... 행렬을 쓰면 엣지 보는 횟수가 전체 m개밖에 안되겟네요.. 감사합니다!!


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