BOJ 18083 - Disposable Switches (D5)

지금까지 푼 CHT 문제들 중에 CHT를 가장 특이하게 쓰는 것 같다.

 

사용 알고리즘

dp, Convex Hull Trick

 

풀이

가장 먼저 관찰해야 하는 사실은 v가 영향을 줄 수 없다는 것이다. 왜냐하면 v>0이므로 처음부터 v가 나눠져 있었다고 생각하면 된다.

결국 각 간선의 가중치는 l + c가 되고, 최단 경로의 간선 개수에 영향을 받음을 알 수 있다. 이제 다음과 같은 dp를 정의하자.

dp[i][j] := 1번 정점에서 i번 정점까지 도달하는 데에 j개의 간선을 사용했을 때의 최단 경로

이는 O(N(N+M))에 계산할 수 있다. (다익스트라를 이용한 O(N(N+M)logNM)은 TLE를 받는다.)

이렇게 구한 dp[n][i](1 <= i <= n-1)에 대하여

f_i(x) = i*x + dp[n][i]라는 직선을 생각해보자. 이 직선이 의미하는 바는 "n번 정점까지 갈 때 i개의 간선을 사용한 최단 경로에 대하여 c = x일 때의 가중치"이다. 만약 f_i(x') <= min(f_j(x'))인 x'이 존재한다면 이 직선은 c = x'에서 최단 경로가 될 수 있으므로  "n번 정점까지 갈 때 i개의 간선을 사용한 최단 경로"를 통해 네트워크가 이동할 수 있다. 따라서 이 경로에 속하는 모든 정점을 답의 후보에서 제외할 수 있다. 결국 어떤 직선이 최적이 될 수 있는 x가 존재하는지를 판별하는 문제가 되는데, 이는 CHT 내부에 직선이 존재함과 동치이므로 CHT에 기울기가 큰 순서대로 직선을 넣은 후 마지막에 살아있는 모든 직선에 대해서 위와 같은 과정을 시행하면 된다. 이는 bfs 등으로 해줄 수 있다.

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#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 1000000007
#define MOD2 998244353
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define sz(x) (ll)x.size()
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef __int128_t lll;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> PP;
const ll inf = 1e18;
ll n,m;
ll dp[2001][2001];
vector<pi> adj[2001];
struct Line{
    ll a,b;
    ll f(ll x){ return a*x+b; }
};
ld cross(Line a, Line b){ return 1.0 * (a.b-b.b)/(b.a-a.a); }
ld s[2001]; Line stk[2001]; ll siz; ll save[2001];
void insert(Line k, ll a){  //k : ax + dp[a][n]
    while(siz){
        s[siz] = cross(k,stk[siz-1]);
        if(s[siz]<s[siz-1])siz--;
        else break;
    }
    stk[siz] = k, save[siz++] = a;
}
bool vis[2001][2001];
int main(){
    fast;
    cin>>n>>m;
    for(int i = 1 ; i <= m ; i++){
        ll a,b,c; cin>>a>>b>>c; adj[a].push_back({b,c}); adj[b].push_back({a,c});
    }
    memset(dp,-1,sizeof(dp));
    dp[1][0] = 0;
    for(int j = 1 ; j < n ; j++){
        for(int i = 1 ; i <= n ; i++){
            for(auto [next,w] : adj[i])if(dp[next][j-1]>=0)dp[i][j] = (dp[i][j]<0 ? dp[next][j-1]+w : min(dp[i][j],dp[next][j-1]+w));
        }
    }
    for(int i = n-1 ; i >= 1 ; i--)if(dp[n][i]>=0)insert({i, dp[n][i]}, i);
    queue<pi> q; for(int i = 0 ; i < siz ; i++)q.push({n, save[i]}), vis[n][save[i]] = 1;
    while(sz(q)){
        auto [cur, e] = q.front(); q.pop();
        if(!e)continue;
        for(auto [next,w] : adj[cur])if(!vis[next][e-1] and dp[next][e-1]>=0 and dp[next][e-1] + w == dp[cur][e]){
            vis[next][e-1] = 1; q.push({next,e-1});
        }
    }
    vector<ll> ans;
    for(int i = 1 ; i <= n ; i++){
        ans.push_back(i);
        for(int j = 0 ; j < n ; j++)if(vis[i][j]){
            ans.pop_back(); break;
        }
    }
    cout<<sz(ans)<<"\n";
    for(auto i : ans)cout<<i<<" ";
}