백준12880 그래프 차이 최소

작성일 | In

문제 링크

  • http://icpc.me/12880

사용 알고리즘

  • DFS

시간복잡도

  • $O(N^4)$

풀이

간선 가중치의 상한과 하한을 고정시킨 다음 DFS를 돌리는 것을 반복하면 됩니다.

하지만 가능한 상한이 150,000가지, 하한도 150,000가지이므로 TLE가 나게 됩니다. 최적화를 합시다.

가중치의 종류는 최대 $N^2$개입니다. 좌표압축을 해줍시다.
이제 가능한 상한이 $N^2$개, 하한이 $N^2$개, DFS를 하는데 $O(N^2)$으로 총 $O(N^6)$에 풀 수 있습니다.

하지만 상한을 고정시켰을 때 하한을 $N^2$가지를 모두 보는 것이 아니라 투포인터 느낌으로 보면 $O(N^2)$을 떼어줄 수 있습니다.
$O(N^4)$에 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, g[55][55], cnt;
bool chk[55];
vector<int> comp;

void dfs(int v, int l, int r, int flag){
    cnt++; chk[v] = 1;
    for(int i=1; i<=n; i++){
        if(flag) if(!chk[i] && l <= g[v][i] && g[v][i] <= r) dfs(i, l, r, flag);
        if(!flag) if(!chk[i] && l <= g[i][v] && g[i][v] <= r) dfs(i, l, r, flag);
    }
}

int valid(int l, int r){
    memset(chk, 0, sizeof chk); cnt = 0;
    dfs(1, l, r, 0);
    if(cnt != n) return 0;
    memset(chk, 0, sizeof chk); cnt = 0;
    dfs(1, l, r, 1);
    return cnt == n;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; comp.reserve(n*n);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> g[i][j], comp.push_back(g[i][j]);
    compress(comp);

    int mn = 1e9+7, l = 0, r = 0;
    for(; r<comp.size(); r++) for(; l<=r; l++){
        if(valid(comp[l], comp[r])) mn = min(mn, comp[r] - comp[l]);
        else break;
    }
    cout << mn;
}