QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#383852 | #961. Smol Vertex Cover | KLPP# | RE | 0ms | 0kb | C++23 | 6.9kb | 2024-04-09 18:10:58 | 2024-04-09 18:10:58 |
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
// 1-based nodes; use -u to represent 'not u'
struct TwoSAT {
int n;
vector<vector<int>> adj, radj;
vector<int> scc_id, topsort, answer;
vector<bool> visited;
TwoSAT() {}
TwoSAT(int _n) {
n = _n;
adj.resize(2*n+1), radj.resize(2*n+1);
scc_id.resize(2*n+1), answer.resize(2*n+1), visited.resize(2*n+1);
}
void init(int _n){
n = _n;
adj.clear();
radj.clear();
scc_id.clear();
answer.clear();
visited.clear();
adj.resize(2*n+1), radj.resize(2*n+1);
scc_id.resize(2*n+1), answer.resize(2*n+1), visited.resize(2*n+1);
}
void add_edge(int a, int b) {
int not_a = a<0 ? -a : a+n;
int not_b = b<0 ? -b : b+n;
if (a<0) a=n-a;
if (b<0) b=n-b;
adj[a].pb(b);
adj[not_b].pb(not_a);
radj[b].pb(a);
radj[not_a].pb(not_b);
}
void add_or(int a, int b) { add_edge(-a, b); }
void add_xor(int a, int b) { add_or(a, b); add_or(-a, -b); }
void add_imply(int a, int b) { add_edge(a, b); }
void add_equivalent(int a, int b) { add_imply(a, b); add_imply(b, a); }
void force_true(int a) { add_or(a, a); }
void force_false(int a) { add_or(-a, -a); }
void dfs(int u) {
visited[u] = true;
for (int v : adj[u]) if (!visited[v]) dfs(v);
topsort.pb(u);
}
void rdfs(int u, int scc) {
visited[u] = true;
scc_id[u] = scc;
for (int v : radj[u]) if (!visited[v]) rdfs(v, scc);
}
// Returns whether the formula is satisfiable and, if so, puts in 'answer' a satisfying assignment.
bool solve() {
fill(all(visited), false);
for (int i = 1; i <= 2*n; i++) if (!visited[i]) dfs(i);
reverse(all(topsort));
fill(all(visited), false);
int scc = 0;
for (int u : topsort) if (!visited[u]) rdfs(u, scc++);
for (int i = 1; i <= n; i++) {
if (scc_id[i] == scc_id[i+n]) return false;
answer[i] = scc_id[i] > scc_id[i+n];
}
return true;
}
};
// General matching (Edmonds' blossom algorithm) in O(N^3).
struct Blossom {
int n, m; // number of vertices and blossoms (not edges!)
vector<int> mate, p, d, bl;
vector<vector<int>> b, adj;
Blossom(int _n) {
n = _n, m = n + n/2; // m = 3n/2
mate.assign(n, -1);
b.resize(m), p.resize(m), d.resize(m), bl.resize(m);
adj.assign(m, vector<int>(m, -1));
}
void add_edge(int u, int v) { adj[u][v] = u; adj[v][u] = v; }
void match(int u, int v) { adj[u][v] = adj[v][u] = -1; mate[u]=v; mate[v]=u; }
vector<int> trace(int x) {
vector<int> vx;
while (1) {
while (x != bl[x]) x = bl[x];
if (!vx.empty() && vx.back() == x) break;
vx.push_back(x);
x = p[x];
}
return vx;
}
void contract(int c, vector<int> &vx, vector<int> &vy) {
b[c].clear();
int r = vx.back();
while (!vx.empty() && !vy.empty() && vx.back() == vy.back()) {
r = vx.back(), vx.pop_back(), vy.pop_back();
}
b[c].push_back(r);
b[c].insert(b[c].end(), vx.rbegin(), vx.rend());
b[c].insert(b[c].end(), vy. begin(), vy. end());
for (int i = 0; i <= c; i++) adj[c][i] = adj[i][c] = -1;
for (int z : b[c]) {
bl[z] = c;
for (int i = 0; i < c; i++) if (adj[z][i] != -1) {
adj[c][i] = z; adj[i][c] = adj[i][z];
}
}
}
vector<int> lift(vector<int> &vx) {
vector<int> A;
while (sz(vx) >= 2) {
int z = vx.back(); vx.pop_back();
if (z < n) { A.push_back(z); continue; }
int w = vx.back();
int i = int(~sz(A)&1 ? find(all(b[z]), adj[z][w])-b[z].begin():0);
int j = int( sz(A)&1 ? find(all(b[z]), adj[z][A.back()])-b[z].begin():0);
int k = sz(b[z]);
int dif = (~sz(A)&1 ? i&1 : ~j&1) ? 1 : k-1;
while (i != j) vx.push_back(b[z][i]), i = (i+dif)%k;
vx.push_back(b[z][i]);
}
return A;
}
int solve() {
for (int ans = 0; ; ans++) {
fill(all(d), 0);
queue<int> q;
for (int i = 0; i < m; i++) bl[i] = i;
for (int i = 0; i < n; i++) if (mate[i]==-1) q.push(i), p[i]=i, d[i]=1;
int c = n;
bool aug = false;
while (!q.empty() && !aug) {
int x = q.front(); q.pop();
if (x != bl[x]) continue;
for (int y = 0; y < c; y++) {
if (y == bl[y] && adj[x][y] != -1) {
if (d[y]==0) {
p[y]=x, d[y]=2, p[mate[y]]=y, d[mate[y]]=1;
q.push(mate[y]);
}
else if (d[y]==1) {
vector<int> vx = trace(x);
vector<int> vy = trace(y);
if (vx.back() == vy.back()) {
contract(c, vx, vy);
q.push(c);
p[c] = p[b[c][0]];
d[c] = 1;
c++;
}
else {
aug = true;
vx.insert(vx.begin(), y); vy.insert(vy.begin(), x);
vector<int> A = lift(vx), B = lift(vy);
A.insert(A.end(), B.rbegin(), B.rend());
for (int i = 0; i < sz(A); i += 2) {
match(A[i], A[i+1]);
if (i+2 < sz(A)) add_edge(A[i+1], A[i+2]);
}
}
break;
}
}
}
}
if (!aug) return ans;
}
}
};
vector<int> nei[10000];
void solve(){
int n, m; cin >> n >> m; // vertices and edges
Blossom B(n);
for (int i = 0; i < m; i++) { int a, b; cin >> a >> b;a--,b--;nei[a].push_back(b),nei[b].push_back(a); B.add_edge(a, b); }
B.solve();
vector<pair<int,int> >match;
vector<bool> nmatch(n,true);
for (int i = 0; i < n; i++)
if (i < B.mate[i])match.push_back({i,B.mate[i]}),nmatch[i]=false,nmatch[B.mate[i]]=false;
//trav(a,match)cout<<a.first<<" "<<a.second<<endl;
TwoSAT T1(n);
rep(i,0,n){
if(nmatch[i])T1.add_imply(i+1,-i-1);
trav(a,nei[i]){
T1.add_or(i+1,a+1);
}
}
trav(a,match)T1.add_xor(a.first+1,a.second+1);
if(T1.solve()){
cout<<match.size()<<"\n";
rep(i,0,n){
if(T1.answer[i+1])cout<<i+1<<" ";
}
cout<<"\n";
return;
}
rep(Fx,0,n){
T1.init(n);
if(nmatch[Fx]){
rep(i,0,n){
if(nmatch[i] && i!=Fx)T1.add_imply(i+1,-i-1);
trav(a,nei[i]){
T1.add_or(i+1,a+1);
}
}
trav(a,match)T1.add_xor(a.first+1,a.second+1);
bool ans=T1.solve();
//cout<<"A"<<ans<<" "<<Fx<<endl;
if(ans){
cout<<match.size()<<"\n";
rep(i,0,n){
if(T1.answer[i+1])cout<<i+1<<" ";
}
cout<<"\n";
return;
}
}else{
rep(i,0,n){
if(nmatch[i])T1.add_imply(i+1,-i-1);
trav(a,nei[i]){
T1.add_or(i+1,a+1);
}
}
trav(a,match){
if(a.first!=Fx && a.second!=Fx)T1.add_xor(a.first+1,a.second+1);
}
bool ans=T1.solve();
//cout<<"A"<<ans<<" "<<Fx<<endl;
if(ans){
cout<<match.size()<<"\n";
rep(i,0,n){
if(T1.answer[i+1])cout<<i+1<<" ";
}
cout<<"\n";
return;
}
}
}
cout<<"not smol\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;
cin>>tt;
while(tt--){
solve();
}
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
5 5 1 2 2 3 3 4 4 5 1 5