卧薪尝胆,厚积薄发。
酒店之王
Date: Fri Sep 07 17:11:01 CST 2018 In Category: NoCategory

Description:

每个人有喜欢的房间和喜欢的菜,选出 $p$ 个房间和 $q$ 道菜使得满足的人最多。
$1\le n \le 100$

Solution:

把人拆点放在中间,把房间和菜分别放在左右,源点和房间,房间和人,人和菜,菜和汇点依次连边求最大流。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
inline int read()
{
register int res = 0;
register char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))
{
res = (res << 1) + (res << 3) + c - '0';
c = getchar();
}
return res;
}
int n,p,q;
#define MAXN 110
int s,t;
struct edge
{
int to,nxt,f;
}e[MAXN * 3 * 2 + MAXN * MAXN * 2 * 2];
int edgenum = 0;
int lin[MAXN * 4];
void add(int a,int b,int f)
{
e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;
e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;
return;
}
int ch[MAXN * 4];
#define INF 0x3f3f3f3f
bool BFS()
{
queue<int> q;
memset(ch,-1,sizeof(ch));
q.push(s);ch[s] = 0;
while(!q.empty())
{
int k = q.front();q.pop();
for(int i = lin[k];i != -1;i = e[i].nxt)
{
if(ch[e[i].to] == -1 && e[i].f)
{
ch[e[i].to] = ch[k] + 1;
q.push(e[i].to);
}
}
}
return (ch[t] != -1);
}
int flow(int k,int f)
{
if(k == t)return f;
int r = 0;
for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)
{
if(ch[e[i].to] == ch[k] + 1 && e[i].f)
{
int l = flow(e[i].to,min(f - r,e[i].f));
e[i].f -= l;r += l;e[i ^ 1].f += l;
}
}
if(r == 0)ch[k] = -1;
return r;
}
int dinic()
{
int ans = 0,r;
while(BFS())while(r = flow(s,INF))ans += r;
return ans;
}
int main()
{
memset(lin,-1,sizeof(lin));
scanf("%d%d%d",&n,&p,&q);
s = n + n + p + q + 1;t = s + 1;
for(int i = 1;i <= p;++i)add(s,i + n + n,1);
for(int i = 1;i <= q;++i)add(i + n + n + p,t,1);
for(int i = 1;i <= n;++i)add(i,i + n,1);
int k;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= p;++j)
if(read() == 1)add(j + n + n,i,1);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= p;++j)
if(read() == 1)add(i + n,j + n + n + p,1);
cout << dinic() << endl;
return 0;
}
In tag: 图论-dinic
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡