Description
Input
Output
Sample Input
2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1
Sample Output
YES NO
题目一看就知道是求二分图的最大匹配，看看最大匹配是不是等于P，那么就简单咯，可以用匈牙利算法，最大流算法来求，还有一个优化的地方，如果P大于N的话，直接输出NO
#include<map> #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 0x0f0f0f0f using namespace std; struct Edge { int from,to,cap,flow; }; struct DINIC{ static const int maxn=2500+10; int n,m,s,t; vector<Edge>edges; vector<int>G[maxn]; int d[maxn],cur[maxn]; bool vis[maxn]; void AddEdge(int from,int to,int cap) { Edge temp; temp.cap=cap; temp.flow=0; temp.from=from; temp.to=to; edges.push_back(temp); temp.cap=0; temp.flow=0; temp.from=to; temp.to=from; edges.push_back(temp); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(s); d[s]=0; vis[s]=1; while(!Q.empty()) { int x=Q.front();Q.pop(); for (int i=0;i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if (!vis[e.to] && e.cap>e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if (x==t || a==0) return a; int flow=0,f; for (int& i=cur[x];i<G[x].size();i++) { Edge& e=edges[G[x][i]]; if (d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if (a==0) break; } } return flow; } int Dinic() { int flow=0; while (BFS()) { memset(cur,0,sizeof(cur)); flow+=DFS(s,inf); } return flow; } void init() { for (int i=0;i<=maxn;i++) G[i].clear(); edges.clear(); } }; DINIC represent; int main() { //freopen("in.txt","r",stdin); int N,P,x,num,Case; scanf("%d",&Case); while(Case--) { scanf("%d%d",&P,&N); represent.n=P+N; represent.init(); for (int i=1;i<=P;i++) { represent.AddEdge(0,i,1); scanf("%d",&num); while(num--) { scanf("%d",&x); represent.AddEdge(i,P+x,1); } } int T=P+N+1; for (int i=P+1;i<=P+N;i++) { represent.AddEdge(i,T,1); } represent.s=0; represent.t=T; if (P>N) { printf("NO\n"); continue; } int ans=represent.Dinic(); if (ans==P) printf("YES\n"); else printf("NO\n"); } return 0; }
poj 1469 COURSES,布布扣,bubuko.com
原文：http://www.cnblogs.com/chensunrise/p/3776501.html