首页 > 代码库 > 课程-二分图
课程-二分图
http://www.luogu.org/problem/show?pid=2417#sub
题目描述
n个学生去p个课堂，每一个学生都有自己的课堂，并且每个学生只能去一个课堂，题目要求能够安排每一个课堂都有人吗？
输入输出格式
输入格式：
第一行是测试数据的个数，
每组测试数据的开始分别是p和n，
接着p行，每行的开始是这个课堂的学生人数m，接着m个数代表该课堂的学生编号
输出格式：
如果该组数据能够这样安排就输出YES，否则输出NO。
经典模型，建二分图，根据学生和教室的关系，连容量为1的边，再增加S和T点，分别用容量1的边连所有学生和所有教室，跑一遍最大流，判断最大流是否等于教室数（当然可以用其他方法求最大匹配，不一定要用S,T点连边）
1 #include<iostream> 2 #include<vector> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 const int maxn=100010; 7 const int inf=1<<30; 8 struct Edge{ 9 int from,to,flow,cap;10 };11 struct Dinic{12 int vis[maxn],cur[maxn],d[maxn];13 vector<Edge> edges;14 vector<int> G[maxn];15 int s,t;16 void clear()17 {18 for(int i=0;i<maxn;i++) G[i].clear();19 edges.clear();20 }21 void addEdge(int from,int to,int cap)22 {23 edges.push_back((Edge){from,to,0,cap});24 G[from].push_back(edges.size()-1);25 edges.push_back((Edge){to,from,0,0});26 G[to].push_back(edges.size()-1);27 }28 int BFS()29 {30 memset(vis,0,sizeof(vis));31 queue<int> Q;32 Q.push(s);33 vis[s]=1;34 d[s]=0;35 while(!Q.empty()){36 int x=Q.front();Q.pop();37 for(int i=0;i<G[x].size();i++){38 Edge& e=edges[G[x][i]];39 if(!vis[e.to]&&e.cap>e.flow){40 vis[e.to]=1;41 d[e.to]=d[x]+1;42 Q.push(e.to);43 }44 }45 }46 return vis[t];47 }48 int DFS(int u,int a)49 {50 if(u==t||a==0) return a;51 int flow=0,f;52 for(int& i=cur[u];i<G[u].size();i++){53 Edge& e=edges[G[u][i]];54 if(d[e.to]==d[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){55 e.flow+=f;56 edges[G[u][i]^1].flow-=f;57 flow+=f;58 a-=f;59 if(!a) break;60 }61 }62 return flow;63 }64 int MaxFlow(int ss,int tt)65 {66 int ans=0;67 s=ss,t=tt;68 while(BFS()){69 memset(cur,0,sizeof(cur));70 ans+=DFS(s,inf);71 }72 return ans;73 }74 };75 Dinic solver;76 int main()77 {78 int n,p,T,m,a;79 cin>>T;80 while(T--)81 {82 solver.clear();83 cin>>p>>n;84 for(int i=2;i<=n+1;i++) solver.addEdge(1,i,1);85 for(int i=n+2;i<=n+p+1;i++) solver.addEdge(i,n+p+2,1);86 for(int i=1;i<=p;i++){87 cin>>m;88 while(m--){89 cin>>a;90 solver.addEdge(a+1,n+i+1,1);91 }92 }93 if(solver.MaxFlow(1,n+p+2)==p) cout<<"YES\n";94 else cout<<"NO\n";95 }96 return 0;97 }
课程-二分图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。