hdu - 3498 - whosyourdaddy（重復(fù)覆蓋DLX）
來源：程序員人生 發(fā)布時(shí)間：2014-11-07 08:31:03 閱讀次數(shù)：2128次
題意：N(2 ≤ N ≤ 55)個(gè)點(diǎn)，M(0 ≤ M ≤ N*N)條無向邊，刪除1個(gè)點(diǎn)會(huì)把與其相鄰的點(diǎn)1起刪掉，問最少刪幾次可以刪掉所有點(diǎn)。
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3498
――>>N個(gè)點(diǎn)看成 N 個(gè)要被覆蓋的列，每一個(gè)點(diǎn)作為1行，與其相鄰的點(diǎn)的位置在這1行中標(biāo)為 1，還有它自已的位置也標(biāo)記為 1。。
這就是經(jīng)典的重復(fù)覆蓋問題了。。因而，DLX上場。。
#include <cstdio>
#include <cstring>
const int MAXR = 55 + 10;
const int MAXC = 55 + 10;
const int MAXNODE = MAXR * MAXC;
const int INF = 0x3f3f3f3f;
struct DLX
{
int sz;
int H[MAXR], S[MAXC];
int row[MAXNODE], col[MAXNODE];
int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];
int Min;
void Init(int n)
{
for (int i = 0; i <= n; ++i)
{
U[i] = D[i] = i;
L[i] = i - 1;
R[i] = i + 1;
}
L[0] = n;
R[n] = 0;
sz = n + 1;
memset(S, 0, sizeof(S));
memset(H, ⑴, sizeof(H));
}
void Link(const int& r, const int& c)
{
row[sz] = r;
col[sz] = c;
D[sz] = D[c];
U[D[c]] = sz;
D[c] = sz;
U[sz] = c;
if (H[r] == ⑴)
{
H[r] = L[sz] = R[sz] = sz;
}
else
{
R[sz] = R[H[r]];
L[R[H[r]]] = sz;
R[H[r]] = sz;
L[sz] = H[r];
}
S[c]++;
sz++;
}
void Remove(const int& c)
{
for (int i = D[c]; i != c; i = D[i])
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
}
void Restore(const int& c)
{
for (int i = U[c]; i != c; i = U[i])
{
L[R[i]] = i;
R[L[i]] = i;
}
}
int A()
{
int ret = 0;
bool vis[MAXC];
memset(vis, 0, sizeof(vis));
for (int i = R[0]; i != 0; i = R[i])
{
if (!vis[i])
{
vis[i] = true;
++ret;
for (int j = D[i]; j != i; j = D[j])
{
for (int k = R[j]; k != j; k = R[k])
{
vis[col[k]] = true;
}
}
}
}
return ret;
}
void Dfs(int cur)
{
if (cur + A() >= Min) return;
if (R[0] == 0)
{
if (cur < Min)
{
Min = cur;
}
return;
}
int c = R[0];
for (int i = R[0]; i != 0; i = R[i])
{
if (S[i] < S[c])
{
c = i;
}
}
for (int i = D[c]; i != c; i = D[i])
{
Remove(i);
for (int j = R[i]; j != i; j = R[j])
{
Remove(j);
}
Dfs(cur + 1);
for (int j = L[i]; j != i; j = L[j])
{
Restore(j);
}
Restore(i);
}
}
void Solve()
{
Min = INF;
Dfs(0);
printf("%d
", Min);
}
} dlx;
int N, M;
void Read()
{
int a, b;
dlx.Init(N);
while (M--)
{
scanf("%d%d", &a, &b);
dlx.Link(a, b);
dlx.Link(b, a);
}
for (int i = 1; i <= N; ++i)
{
dlx.Link(i, i);
}
}
int main()
{
while (scanf("%d%d", &N, &M) == 2)
{
Read();
dlx.Solve();
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
