QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#351405#961. Smol Vertex Coverchenxinyang2006#WA 0ms7940kbC++145.0kb2024-03-11 21:38:242024-03-11 21:38:26

Judging History

你现在查看的是最新测评结果

  • [2024-03-11 21:38:26]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7940kb
  • [2024-03-11 21:38:24]
  • 提交

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