本题和教辅的组成有几分相似。
#include#include #include #include #include using namespace std;inline int read(){ int t=1,num=0; char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')t=-1;c=getchar();} while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();} return num*t;}const int INF=10000010;struct edge{ int to;int c;int rev;};vector g[501];int n,p,q,iter[501],level[501];void add(int f,int t,int c){ g[f].push_back((edge){t,c,g[t].size()}); g[t].push_back((edge){f,0,g[f].size()-1});}void bfs(int s){ memset(level,0,sizeof(level)); queue q; level[s]=1; q.push(s); while(!q.empty()){ int v=q.front();q.pop(); for(int i=0;i 0&&level[e.to]==0){ level[e.to]=level[v]+1; q.push(e.to); } } }}int dfs(int v,int t,int f){ if(v==t) return f; for(int &i=iter[v];i 0&&level[v]+1==level[e.to]){ int d=dfs(e.to,t,min(f,e.c)); if(d>0){ e.c-=d; g[e.to][e.rev].c+=d; return d; } } } return 0;}int flow(int s,int t){ int flow=0; while(1){ bfs(s); if(level[t]==0) return flow; memset(iter,0,sizeof(iter)); int f; while((f=dfs(s,t,INF))>0)flow+=f; }}int main(){ int lala,t; n=read();p=read();q=read(); t=n+n+p+q+1; for(int i=1;i<=n;i++)add(i,i+n,1); for(int i=1;i<=n;i++){ for(int j=1;j<=p;j++){ lala=read(); if(lala)add(j+n+n,i,1); } } for(int i=1;i<=n;i++){ for(int j=1;j<=q;j++){ lala=read(); if(lala)add(i+n,j+n+n+p,1); } } for(int i=1;i<=p;i++)add(0,n+n+i,1); for(int i=1;i<=q;i++)add(n+n+p+i,t,1); printf("%d\n",flow(0,t)); return 0;}
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。