神奇

回复帖子

@Wakelin 2018-10-22 11:18 回复

80分代码:

#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cctype>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 20010;
int T, n, p;
int vis[MAXN], f[MAXN];

struct Edge {
    int to, nxt, val;
}e[MAXN << 2];

template <typename _Tp>
inline void read(_Tp &x) {
    char ch = getchar( ); bool f = 0; x = 0;
    while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar( ); }
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar( );
    x = f ? -x : x;
}

int head[MAXN], tot;
inline void AddEdge(int x, int y) {
    e[++ tot].to = y, e[tot].nxt = head[x], head[x] = tot;
}

void Clear( ) {
    memset(f, 0, sizeof(f));
    memset(e, 0, sizeof(e));
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    tot = 0;
}

bool Dfs(int x, int t) {
    for (int i = head[x], v; ~i; i = e[i].nxt) {
        v = e[i].to;
        if (vis[v] ^ t) {
            vis[v] = t;
            if (!f[v] || Dfs(f[v], t)) {
                f[v] = x;
                return true;
            }
        }
    } return false;
}

int main() {
    read(T);
    while (T -- ) {
    Clear( );
    read(p), read(n);
    int x, m;
    for (int i = 1; i <= p; ++ i) {
        read(m);
        for (int i = 1; i <= m; ++ i) {
            read(x);
            AddEdge(i, x);
        }
    }
    if (p > n) { 
        printf("NO\n"); 
        continue; 
    }
    int ans = 0;
    for (int i = 1; i <= p; ++ i) 
        if (Dfs(i, i)) ans ++;  
    if (ans == p) printf("YES\n");
    else printf("NO\n");
    }
    return 0;
}

调了半天发现是主函数里的读入错了

    for (int i = 1; i <= p; ++ i) {
        read(m);
        for (int i = 1; i <= m; ++ i) {
        // => for (int j = 1; j <= m; ++ j) {
            read(x);
            AddEdge(i, x);
        }
    }

没CE?for循环里能重复定义??? 调试发现i一直从1~m,重复p遍。这么神奇?

@RiverFun 2018-10-22 11:31 回复 举报

@W_Excalibur

我已经这么错过好几次了,其中一个原因就是因为这样写不会CE

不过你这样还能得80分真是令人惊奇

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。