BOJ 18770 - 불안정한 물질 (P2)

#dfs #tree-dp

 

구현이 짜증나는 문제다.

문제는 꽤 재밌는데, n개의 노드와 n개의 간선이 있다. 이상태에서 인접하지 않은 정점만 골라서 최대 점수를 얻는 문제다.

만약 n개의 노드가 다 연결되어 있다면 그 그래프는 트리에 하나의 간선을 추가한 형태일 것이고, 그 간선에 의해 indegree가 2인 정점이 생긴다.

그래서 이 정점과 그 부모를 골라내서 이 정점들끼리는 미리 고를지 말지를 결정해두고, 간선을 하나 지우면 트리가 된다. 그 이후로 트리 dp를 돌리면 된다.

과연 이게 가능할까? 생각해보면 트리에서 간선만 하나 추가한 형태이기 때문에, 고려할 정점은 무조건 3개이다. 그래서 이 3개끼리 잘 케이스를 나눠가면서 연결그래프를 유지하되 간선을 하나 지울 수 있다. 그러면 트리가 되므로 2^3개의 경우의 수를 모두 따져보면서, 각 정점들을 골랐을 때 문제가 없다면(고려하는 정점끼리 인접하지 않음) 그 상태에서 tree dp를 적용하면 된다.

문제는 연결 그래프가 아닐 수 있다는건데, 서브그래프도 모두 정점과 간선의 개수가 똑같은 형태이니 똑같이 적용하면 된다.

다중간선 때문에 약간 예외처리가 필요할 수 있고, 아마 구현은 겁나 귀찮을 것이다. 그래서 그냥 다른 풀이를 찾는 것을 추천한다.

(언젠가 사진 추가 예정)

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
using namespace std;
ll n;
ll w[101010];
map<ll,bool> m;
vector<ll> adj[101010], tmp[101010];
vector<ll> v;
ll dp[101010][2];
ll ind[101010];
bool visited[101010], finished[101010];
void maketree(ll x, ll par){
    visited[x]=1;
    v.push_back(x);
    for(auto next : tmp[x]){
        if(next==par)continue;
        if(!visited[next]){
            ind[next]++;
            adj[x].push_back(next);
            maketree(next, x);
        }
        else if(finished[next]){
            ind[next]++;
            adj[x].push_back(next);
        }
    }
    finished[x]=1;
}
ll dfs(ll node, bool par){
    ll &ret = dp[node][par];
    if(~ret)return ret;
    ret = 0;
    bool flag = 0;
    if(m.find(node)!=m.end()){
        flag = m[node];
        ret = (flag ? w[node] : 0);
        for(auto next : adj[node]){
            ret += dfs(next, flag);
        }
        return ret;
    }
    for(auto next : adj[node]){
        if(m.find(next)!=m.end()){
            if(m[next]==1)flag = 1;
        }
    }
    if(flag==1 or par==1){    //next에 m[node]=1인 정점 존재 -> 현재 노드 포함 x or parent가 1이어서 반드시 포함 x
        ret = 0;
        for(auto next : adj[node]){
            ret += dfs(next, 0);
        }
        return ret;
    }
    if(adj[node].empty())return ret = (par ? 0 : w[node]);
    //case 1 : 현재 노드를 포함하지 않는 경우
    for(auto next : adj[node]){
        ret += dfs(next, 0);
    }
    //2 : 포함하는 경우
    ll ret2 = w[node];
    for(auto next : adj[node]){
        ret2 += dfs(next, 1);
    }
    return ret = max(ret, ret2);
}
void dfs2(ll x){
    visited[x]=1;
    for(auto next : adj[x])if(!visited[next])dfs2(next);
}
int main(){
    fast;
    ll t; cin>>t;
    while(t--){
        cin>>n;
        for(int i = 1 ; i <= n ; i++)ind[i]=finished[i]=0,tmp[i].clear();
        for(int i = 1 ; i <= n ; i++){
            cin>>w[i];
            adj[i].clear();
            visited[i]=0;
            ll a; cin>>a;
            tmp[i].push_back(a);
            tmp[a].push_back(i);
        }
        for(int i = 1 ; i <= n ; i++){
            sort(all(tmp[i]));
            comp(tmp[i]);
        }
        vector<vector<ll>> group;
        for(int i = 1 ; i <= n ; i++){
            if(!visited[i]){
                v.clear();
                maketree(i,0), group.push_back(v);
            }
        }
        ll ANS = 0;
        for(auto k : group){
            m.clear();
            set<pair<ll,ll>> s;
            ll cnt=0;
            for(int i = 0 ; i < k.size() ; i++){
                if(ind[k[i]]==2){
                    cnt++;
                    assert(cnt<=1);
                    m[k[i]]=-1;
                    for(auto next : tmp[k[i]]){
                        bool f=0;
                        for(auto cur : adj[next]){
                            if(cur==k[i])f=1;
                        }
                        if(f){
                            if(m.find(next)!=m.end())continue;
                            m[next]=-1;
                        }
                    }
                    for(auto [a,_] : m){
                        for(auto [b,__] : m){
                            if(a>=b)continue;
                            for(auto next : adj[a]){
                                if(next==b){
                                    s.insert({a,b});
                                    break;
                                }
                            }
                            for(auto next : adj[b]){
                                if(next==a){
                                    s.insert({a,b});
                                    break;
                                }
                            }
                        }
                    }
                    for(auto [A,B] : s){
                        bool F=0;
                        for(auto next : adj[A]){
                            if(next==B){
                                F=1;
                                ll j;
                                for(j = 0 ; j < adj[A].size() ; j++){
                                    if(adj[A][j]==B)break;
                                }
                                adj[A].erase(adj[A].begin()+j);
                                for(auto l : k)visited[l]=0;
                                dfs2(k[0]);
                                for(auto l : k)if(!visited[l]){
                                    adj[A].push_back(B);
                                    F=0;
                                    break;
                                }
                                break;
                            }
                        }
                        if(F)break;
                        F=0;
                        for(auto next : adj[B]){
                            if(next==A){
                                F=1;
                                ll j;
                                for(j = 0 ; j < adj[B].size() ; j++){
                                    if(adj[B][j]==A)break;
                                }
                                adj[B].erase(adj[B].begin()+j);
                                for(auto l : k)visited[l]=0;
                                dfs2(k[0]);
                                for(auto l : k)if(!visited[l]){
                                    adj[B].push_back(A);
                                    F=0;
                                    break;
                                }
                                break;
                            }
                        }
                    }
                }
            }
            ll ans=0;
            for(int i = 0 ; i < 8 ; i++){
                ll j =0;
                bool f = 0;
                for(auto &[a,b] : m){
                    if(i&(1<<j))b=1;
                    else b=0;
                    j++;
                }
                for(auto [a,c] : m){
                    for(auto [b,d] : m){
                        if(a>=b)continue;
                        if(c==1 and d==1 and s.find({a,b})!=s.end())f=1;
                    }
                }
                if(f)continue;
                for(auto l : k)dp[l][0]=dp[l][1]=-1, visited[l]=0;
                ans = max(ans, dfs(k[0],0));
            }
            ANS += ans;
        }
        cout<<ANS<<"\n";
    }
}

6852바이트 실화냐(템플릿 때문에 50000바이트인 사람 빼면 꼴지)

디버깅할 때 브루트포스 코드랑 비교해서 1일동안 노가다했다.