TIOJ-1978

, ,

邀請函（Invitation）

https://tioj.ck.tp.edu.tw/problems/1978

Description

給你一張圖，求出最大點獨立集。
點數最多80

Solution

我本來一直以為這題是一般圖最大匹配，不過今天仔細看之後發現不是，而且一般圖沒有最大匹配=最小點覆蓋的結論。
不過有最大點獨立集$+$最小點覆蓋$=|V|$。
吳邦一教授講過關於最小點覆蓋的一個回溯法，於是我想說把他拿來用。

其實這個演算法也很簡單，就每次挑最大degree的點出來要選或者不選就好，這樣的話複雜度聽起來會是$\mathcal{O}(2^n)$之類的。
不過我們可以先做以下幾個處理(簡化)

  1. degree 0的點直接拔掉。
  2. degree 1的點，選他不如選他唯一的鄰居
  3. 剩下假設最大的degree是2，那所有點的degree都是2了，也就是說是一堆環，可以判掉

於是乎我們只剩下最大degree至少是3的case了。
如果不選那個點的話，那他的鄰居都必須要選，可以列出遞迴式$T(n) = T(n-1) + T(n-4) + f(n)$，$n$代表還沒決定要不要選的點的數量，$f(n)$代表維護上面那些東西需要的時間。
解這個遞迴式可以直接DP，或是利用特徵方程式$\lambda^n = \lambda^{n-1} + \lambda^{n-4} \Rightarrow \lambda^4 - \lambda^3 - 1 = 0$，他最大的實根大約是1.38左右，所以我們dfs的複雜度最多是$\mathcal{O}(1.38^n f(n))$。用蠻naive的寫法$f(n)$會是$\mathcal{O}(n)$(我也不知道怎麼快速維護XD)，$n=80$代進去$80 \cdot 1.38^{80}$似乎幾乎是不行，不過不知道為什麼會AC而且竟然只輸BB跟塗大為的submission XD

寫完之後，身為admin看到幾乎所有人都是用random，心情很複雜(#
還有BB跟waynetuinfor的演算法似乎是轉成clique在做，不知道大學打ICPC有沒有機會搞懂。

AC code

  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
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.
 
#ifdef local
#include <bits/extc++.h>
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
using ost = std::ostream;
#define DESTL(STL, BEG, END, OUT) \
    template <typename ...T> ost& operator<<(ost &O, std::STL<T...> v) { int f=0; for(auto x: v) O << (f++ ? ", " : BEG) << OUT; return O << END; }
DESTL(deque, "[", "]", x); DESTL(vector, "[", "]", x);
DESTL(set, "{", "}", x); DESTL(multiset, "{", "}", x); DESTL(unordered_set, "{", "}", x);
DESTL(map , "{", "}", x.first << ":" << x.second); DESTL(unordered_map , "{", "}", x.first << ":" << x.second);
template <typename U, typename V> ost& operator<<(ost &O, std::pair<U,V> p) { return O << '(' << p.first << ',' << p.second << ')'; }
template <typename T, size_t N> ost& operator<<(ost &O, std::array<T,N> a) { int f=0; for(T x: a) O << (f++ ? ", " : "[") << x; return O << "]"; }
template <typename T, size_t ...I> ost& prtuple(ost &O, T t, std::index_sequence<I...>) { return (..., (O << (I ? ", " : "(") << std::get<I>(t))), O << ")"; }
template <typename ...T> ost& operator<<(ost &O, std::tuple<T...> t) { return prtuple(O, t, std::make_index_sequence<sizeof...(T)>()); }
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    (std::cerr << "\033[1;32m(" << s << ") = (" , ... , (std::cerr << args << (--cnt ? ", " : ")\033[0m\n")));
}
#else
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define get_pos(v,x) int(lower_bound(begin(v),end(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define pb emplace_back
#define ff first
#define ss second
#define mem(v,x) memset(v,x,sizeof v)
 
using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T> using max_heap = std::priority_queue<T,vector<T>,less<T> >;
template <typename T> using min_heap = std::priority_queue<T,vector<T>,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
constexpr ld PI = acos(-1), eps = 1e-7;
constexpr ll N = 85, INF = 1e18, MOD = 1000000007, K = 14699, inf = 1e9;
constexpr inline ll cdiv(ll x, ll m) { return x/m + (x%m ? (x<0) ^ (m>0) : 0); } // ceiling divide
constexpr inline ll modpow(ll e,ll p,ll m=MOD) { ll r=1; for(e%=m;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r; }

int n, m;
bool g[N][N];
int picked[N];
int deg[N];
int ans = inf;
void pick(int x) {
    picked[x] = true;
    for(int i = 0; i < n; i++) if(g[x][i]) --deg[i];
}
void unpick(int x) {
    picked[x] = false;
    for(int i = 0; i < n; i++) if(g[x][i]) ++deg[i];
}
void dfs(int c = 0) {
    if(c > ans) return;
    // reduce
    vector<int> zero;
    for(int i = 0; i < n; i++) if(!picked[i] && deg[i] == 0) zero.pb(i);
    if(zero.size()) {
        for(int x: zero) pick(x);
        dfs(c);
        for(int x: zero) unpick(x);
        return;
    }
    for(int i = 0; i < n; i++) if(!picked[i] && deg[i] == 1) {
        for(int j = 0; j < n; j++) if(!picked[j] && g[i][j]) {
            pick(i);
            pick(j);
            dfs(c+1);
            unpick(i);
            unpick(j);
            return;
        }
    }
    int mx = -1;
    for(int i = 0; i < n; i++) if(!picked[i]) {
        if(mx == -1 || deg[i] > deg[mx])
            mx = i;
    }
    if(mx == -1) {
        ans = min(ans, c);
        return;
    }
    vector<int> adj;
    for(int i = 0; i < n; i++) if(!picked[i] && g[mx][i]) adj.pb(i);
    pick(mx);
    dfs(c+1);
    for(int x: adj) pick(x);
    dfs(c+adj.size());
    for(int x: adj) unpick(x);
    unpick(mx);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
        ++deg[a], ++deg[b];
    }
    dfs();
    cout << n - ans << '\n';
}
comments powered by Disqus