酒店只有P间房间,一天只有固定的 q 道不同的菜,每个房间只能住一位客人,每道菜也只能给一位客人食用。
有一天来了 n个客人,每个客人说出了自己喜欢哪些房间,喜欢哪道菜。
怎么分配,能使最多顾客满意呢?
2 2 2 1 0 1 0 1 1 1 1
二分图,
S, 房间,人,食物,T 连边即可
还有,一个人只能匹配一次(yy) ,所以拆点连一条权为1的边
#include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 1e6+2, M=N*2 ; #define int long long int n,p,q; const int inf =1e16; int all=1,hd[N],go[M],w[M],nxt[M]; int S,T; int dis[M],ans=0,now[M]; void add_(int x,int y,int z){ nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=z; swap(x,y); nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=0; } bool bfs(){ for(int i=0;i<M;i++)dis[i]=inf; queue<int> q; q.push(S); now[S]=hd[S]; dis[S]=0; while(q.empty()==0){ int x=q.front(); q.pop(); for(int i=hd[x];i;i=nxt[i]){ int y=go[i]; if(w[i]>0&&dis[y]==inf){ dis[y]=dis[x]+1; now[y]=hd[y]; q.push(y); if(y==T) return 1; } } } return 0; } int dfs(int x,int sum){ if(x==T) return sum; int k,res=0; for(int i=now[x];i&& sum ;i=nxt[i]){ now[x]=i; int y=go[i]; if(w[i]>0&&(dis[y]==dis[x]+1)){ k=dfs(y,min(sum,w[i])); if(k==0) dis[y]=inf; w[i]-=k; w[i^1]+=k; res+=k; sum-=k; } } return res; } void dinic(){ int ans =0; while(bfs()) ans+=dfs(S,inf); cout<<ans<<endl; } signed main(){ int i,j,x; cin>>n>>p>>q; S=0,T=2*n+p+q+1; for(i=1;i<=n;i++) add_(p+i,p+i+n,1); for(i=1;i<=p;i++) add_(S,i,1); for(i=1;i<=q;i++) add_(i+2*n+p,T,1); for(i=1;i<=n;i++) for(j=1;j<=p;j++){ cin>>x; if(x) add_(j,i+p,1); } for(i=1;i<=n;i++) for(j=1;j<=q;j++){ cin>>x; if(x) add_(i+p+n,2*n+p+j,1); } dinic() ; }