hdu 1083 Courses(二分图最大匹配)

    xiaoxiao2021-03-25  74

    看错题目了,送了四发wa,,模板题

    #include <cstdio> #include <cstring> const int MAXN = 500; int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; int p,n; bool dfs(int u) { for(int v = 1;v <= n; ++v) { if(g[u][v] && !used[v]) { used[v] = true; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false; } int hungary() { int res = 0; memset(linker,-1,sizeof(linker)); for(int i = 1; i <= p; ++i) { memset(used,false,sizeof(used)); if(dfs(i)) ++res; } return res; } int main() { int t,a,b; scanf("%d",&t); while(t--) { memset(g,0,sizeof(g)); scanf("%d %d",&p,&n); for(int i = 1; i <= p; ++i) { scanf("%d",&a); while(a--) { scanf("%d",&b); g[i][b] = 1; } } if(hungary() == p) printf("YES\n"); else printf("NO\n"); } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-50173.html

    最新回复(0)