QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#420622 | #961. Smol Vertex Cover | complexor | WA | 1ms | 3940kb | C++14 | 5.6kb | 2024-05-24 20:43:55 | 2024-05-24 20:43:57 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <ctime>
#include <random>
#include <unordered_map>
typedef long long LL;
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pair
int read()
{
int f = 1, s = 0;
char c = getchar();
while (!(c >= '0' && c <= '9'))
f ^= c == '-', c = getchar();
while (c >= '0' && c <= '9')
s = s * 10 + (c ^ 48), c = getchar();
return f ? s : -s;
}
template<typename T>
T& Fmin(T& x, T y){ return x = x < y ? x : y; }
template<typename T>
T& Fmax(T& x, T y){ return x = y < x ? x : y; }
const int MAXN = 1005;
int n, m, mat[MAXN], pre[MAXN], col[MAXN];
std::vector<int> e[MAXN];
namespace DSU
{
int fa[MAXN];
void init(int n){ std::iota(fa + 1, fa + n + 1, 1); }
bool isRoot(int x){ return x == fa[x]; }
int getFath(int x){ return x == fa[x] ? x : (fa[x] = getFath(fa[x])); }
void merge(int x, int y){ fa[getFath(x)] = getFath(y); }
bool tog(int x, int y){ return getFath(x) == getFath(y); }
}
int vis[MAXN], tim = 0;
int q[MAXN], fr, ba;
int getLca(int x, int y)
{
++tim;
while (vis[x] != tim)
{
vis[x] = tim;
x = DSU::getFath(pre[mat[x]]);
if (y) std::swap(x, y);
}
return x;
}
void shrink(int x, int y, int rt)
{
while (!DSU::tog(x, rt))
{
pre[x] = y, y = mat[x];
if (DSU::isRoot(x)) DSU::merge(x, rt);
if (DSU::isRoot(y)) DSU::merge(y, rt);
if (col[y] == 1) col[y] = 0, q[++ba] = y;
x = pre[y];
}
}
bool Blossom(int s)
{
fr = 1, ba = 0;
memset(col + 1, -1, n << 2);
memset(pre + 1, 0, n << 2);
DSU::init(n);
col[q[++ba] = s] = 0;
while (fr <= ba)
{
int x = q[fr++];
for (int y : e[x])
{
if (col[y] == 1 || DSU::tog(x, y)) continue;
if (!col[y])
{
int lca = getLca(x, y);
shrink(x, y, lca), shrink(y, x, lca);
}
else
{
pre[y] = x, col[y] = 1;
if (!mat[y])
{
for (int i = y, j; i; i = j)
j = mat[pre[i]], mat[i] = pre[i], mat[pre[i]] = i;
return true;
}
col[q[++ba] = mat[y]] = 0;
}
}
}
return false;
}
namespace SAT
{
int n, N;
int dfn[MAXN], low[MAXN], st[MAXN], tp, dcnt, bel[MAXN];
bool inSt[MAXN];
std::vector<int> e[MAXN];
void init(int _n)
{
dcnt = 0, tp = 0, n = _n, N = 0;
memset(dfn + 1, 0, n << 3);
for (int i = 1; i <= n + n; i++) e[i].clear();
}
void add(int u, int i, int v, int j){ e[u + i * n].push_back(v + j * n); }
void tarjan(int x)
{
dfn[x] = low[x] = ++dcnt;
inSt[st[++tp] = x] = true;
for (int y : e[x])
if (!dfn[y]) tarjan(y), Fmin(low[x], low[y]);
else if (inSt[y]) Fmin(low[x], dfn[y]);
if (low[x] == dfn[x])
{
++N;
for (int u = 0; u != x; tp--)
inSt[u = st[tp]] = false, bel[u] = N;
}
}
bool sat(bool cho[])
{
for (int i = 1; i <= n + n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++)
if (bel[i] == bel[i + n]) return false;
for (int i = 1; i <= n; i++)
cho[i] = bel[i] > bel[i + n];
return true;
}
}
int con[MAXN][2], K, id[MAXN];
bool cho[MAXN];
bool chk()
{
int cur = 0;
for (int i = 1; i <= n; i++)
if (mat[i] && i < mat[i])
{
con[++cur][0] = i, con[cur][1] = mat[i];
id[i] = cur << 1, id[mat[i]] = cur << 1 | 1;
}
SAT::init(K);
for (int i = 1; i <= K; i++)
for (int o = 0; o <= 1; o++)
{
int x = con[i][o];
for (int y : e[x])
if (!mat[y]) SAT::add(i, o ^ 1, i, o);//, printf("%d %d %d %d\n", i, o, x, y);
else if (y != mat[x])
{
int j = id[y] >> 1, oo = id[y] & 1;
SAT::add(i, o ^ 1, j, oo);
SAT::add(j, oo ^ 1, i, o);
}
}
return SAT::sat(cho);
}
bool chk1(int key)
{
SAT::init(K + 1), SAT::add(K + 1, 1, K + 1, 0);
for (int i = 1; i <= K; i++)
for (int o = 0; o <= 1; o++)
{
int x = con[i][o];
for (int y : e[x])
if (!mat[y] && y != key) SAT::add(i, o ^ 1, i, o);
else if (y != mat[x] && y != key)
{
int j = id[y] >> 1, oo = id[y] & 1;
SAT::add(i, o ^ 1, j, oo);
SAT::add(j, oo ^ 1, i, o);
}
}
return SAT::sat(cho);
}
int main()
{
for (int T = 1; T--; )
{
n = read(), m = read();
for (int i = 1, u, v; i <= m; i++)
{
u = read(), v = read();
e[u].push_back(v), e[v].push_back(u);
}
K = 0;
for (int i = 1; i <= n; i++)
if (!mat[i]) K += Blossom(i);
if (chk())
{
printf("%d\n", K);
for (int i = 1; i <= K; i++)
printf("%d%c", con[i][cho[i]], " \n"[i == K]);
}
else
{
bool vld = false;
for (int i = 1; i <= n; i++)
if (!mat[i] && chk1(i))
{
printf("%d\n", K + 1);
for (int j = 1; j <= K; j++)
printf("%d ", con[j][cho[j]]);
printf("%d\n", i);
vld = true; break;
}
if (!vld) printf("not smol\n");
}
for (int i = 1; i <= n; i++) e[i].clear();
memset(mat + 1, 0, n << 2);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3940kb
input:
5 5 1 2 2 3 3 4 4 5 1 5
output:
3 1 3 5
result:
ok vertex cover of size 3
Test #2:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5
output:
not smol
result:
ok not smol
Test #3:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
3 0
output:
0
result:
ok vertex cover of size 0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
10 10 2 5 3 8 3 10 6 9 1 4 2 6 2 3 4 6 7 10 4 7
output:
5 1 2 3 6 7
result:
ok vertex cover of size 5
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3856kb
input:
10 20 1 9 3 6 3 7 8 9 3 8 1 4 5 10 7 10 4 6 7 9 9 10 2 7 1 6 5 8 2 9 1 7 5 7 3 10 2 6 4 10
output:
not smol
result:
wrong answer vertex cover is smol, but participant did not print it