QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#351405 | #961. Smol Vertex Cover | chenxinyang2006# | WA | 0ms | 7940kb | C++14 | 5.0kb | 2024-03-11 21:38:24 | 2024-03-11 21:38:26 |
Judging History
answer
//输入格式
//第一行两个正整数,n,m。保证 n≥2。n为点数,m为边数
//接下来 m 行,每行两个整数 v,u表示uv之间有边。保证 1≤v,u≤n,保证v≠u,保证同一个条件不会出现两次。
//输出格式
//第一行一个整数,表示最多产生多少个匹配。
//接下来一行 n 个整数,描述一组最优方案。第 v 个整数表示v号点匹配点的编号,如果 v 号没有被匹配输出0
#include <bits/stdc++.h>
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define M 250010
using namespace std;
char inp[33554432], *inpch = inp;
int Head[M], Next[M], Go[M], Pre[510], Nxt[510], F[510], S[510], Q[510], Vis[510], *Top = Q, Cnt = 0, Tim = 0;
int TEST,n, m;
int _u[250005],_v[250005];
inline void addedge(int x, int y) {
Go[++Cnt] = y;
Next[Cnt] = Head[x];
Head[x] = Cnt;
}
int find(int x) {
return x == F[x] ? x : F[x] = find(F[x]);
}
int lca(int x, int y) {
for(Tim++, x = find(x), y = find(y); ; x ^= y ^= x ^= y)
if(x) {
if(Vis[x] == Tim) return x;
Vis[x] = Tim;
x = find(Pre[Nxt[x]]);
}
}
void blossom(int x, int y, int l) {
while(find(x) != l) {
Pre[x] = y;
if(S[Nxt[x]] == 1) S[*Top = Nxt[x]] = 0, *Top++;
if(F[x] == x) F[x] = l;
if(F[Nxt[x]] == Nxt[x]) F[Nxt[x]] = l;
y = Nxt[x];
x = Pre[y];
}
}
int Match(int x) {
for(int i = 1; i <= n; i++) F[i] = i;
memset(S, -1, sizeof S);
S[*(Top = Q) = x] = 0, Top++;
for(int *i = Q; i != Top; *i++)
for(int T = Head[*i]; T; T = Next[T]) {
int g = Go[T];
if(S[g] == -1) {
Pre[g] = *i, S[g] = 1;
if(!Nxt[g]) {
for(int u = g, v = *i, lst; v; u = lst, v = Pre[u])
lst = Nxt[v], Nxt[v] = u, Nxt[u] = v;
return 1;
}
S[*Top = Nxt[g]] = 0, *Top++;
} else if(!S[g] && find(g) != find(*i)) {
int l = lca(g, *i);
blossom(g, *i, l);
blossom(*i, g, l);
}
}
return 0;
}
int ing[505];
vector <int> G[505],R[505];
int N,vis[505],ord[505],fr[505];
void dfs(int u){
// printf("visit %d\n",u);
vis[u] = 1;
for(int v:G[u]){
if(ing[u] || ing[v]) continue;
if(!vis[v]) dfs(v);
}
ord[++N] = u;
}
void dfs2(int u,int c){
fr[u] = c;
for(int v:R[u]){
if(ing[u] || ing[v]) continue;
if(!fr[v]) dfs2(v,c);
}
}
vector <int> answer;
int testify(){
fill(vis,vis + n + 1,0);
fill(fr,fr + n + 1,0);
N = 0;
rep(u,1,n) if(!vis[u]) dfs(u);
rep(u,1,n) if(!fr[ord[u]]) dfs2(ord[u],u);
int fail = 0;
rep(u,1,n){
if(Nxt[u] && fr[u] == fr[Nxt[u]]){
fail = 1;
break;
}
}
if(fail) return 0;
/* rep(u,1,n){
for(int v:G[u]){
if(!ing[u] && !ing[v]) printf("%d %d\n",u,v);
}
}*/
rep(u,1,n) if(ing[u] || (Nxt[u] && fr[u] < fr[Nxt[u]])) answer.eb(u);
printf("%d\n",SZ(answer));
for(int u:answer) printf("%d ",u);
printf("\n");
return 1;
}
void lnk(int u,int v){
// printf("%d %d\n",u,v);
G[u].eb(v);
R[v].eb(u);
}
void solve(){
scanf("%d%d",&n,&m);
Cnt = Tim = 0;
fill(Head,Head + m + 1,0);
memset(Pre,0,sizeof(Pre));
memset(Nxt,0,sizeof(Nxt));
memset(Q,0,sizeof(Q));
memset(F,0,sizeof(F));
memset(S,0,sizeof(S));
memset(Vis,0,sizeof(Vis));
memset(ing,0,sizeof(ing));
rep(i,1,m){
scanf("%d%d",&_u[i],&_v[i]);
addedge(_u[i],_v[i]);
addedge(_v[i],_u[i]);
}
per(i,n,1) if(!Nxt[i]) Match(i);
rep(u,1,n){
G[u].clear();
R[u].clear();
}
rep(i,1,m){
if(!Nxt[_v[i]]) swap(_u[i],_v[i]);
if(!Nxt[_u[i]]){
lnk(_u[i],_v[i]);
lnk(Nxt[_v[i]],_u[i]);
}else{
lnk(Nxt[_u[i]],_v[i]);
lnk(Nxt[_v[i]],_u[i]);
}
}
/* rep(u,1,n){
for(int v:G[u]) printf("%d %d\n",u,v);
}*/
// rep(u,1,n) printf("%d ",Nxt[u]);
// printf("\n");
if(testify()) return;
rep(p,1,n){
if(Nxt[p]){
if(Nxt[p] < p) continue;
ing[p] = ing[Nxt[p]] = 1;
if(testify()) return;
ing[p] = ing[Nxt[p]] = 0;
}else{
ing[p] = 1;
if(testify()) return;
ing[p] = 0;
}
}
printf("not smol\n");
}
int main() {
// freopen("test.in","r",stdin);
scanf("%d",&TEST);
while(TEST--) solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 7940kb
input:
5 5 1 2 2 3 3 4 4 5 1 5
output:
0 1 1 2 1 1 3 1 1 1 4 1 1 1 1
result:
wrong answer not a vertex cover