洛谷P1231 教辅的组成

时间:2023-01-01 16:30:05

题目背景

滚粗了的HansBug在收拾旧语文书,然而他发现了什么奇妙的东西。

题目描述

蒟蒻HansBug在一本语文书里面发现了一本答案,然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数,其中有书,有答案,有练习册。已知一个完整的书册均应该包含且仅包含一本书、一本练习册和一份答案,然而现在全都乱做了一团。许多书上面的字迹都已经模糊了,然而HansBug还是可以大致判断这是一本书还是练习册或答案,并且能够大致知道一本书和答案以及一本书和练习册的对应关系(即仅仅知道某书和某答案、某书和某练习册有可能相对应,除此以外的均不可能对应)。既然如此,HansBug想知道在这样的情况下,最多可能同时组合成多少个完整的书册。

输入输出格式

输入格式:

第一行包含三个正整数N1、N2、N3,分别表示书的个数、练习册的个数和答案的个数。

第二行包含一个正整数M1,表示书和练习册可能的对应关系个数。

接下来M1行每行包含两个正整数x、y,表示第x本书和第y本练习册可能对应。(1<=x<=N1,1<=y<=N2)

第M1+3行包含一个正整数M2,表述书和答案可能的对应关系个数。

接下来M2行每行包含两个正整数x、y,表示第x本书和第y本答案可能对应。(1<=x<=N1,1<=y<=N3)

输出格式:

输出包含一个正整数,表示最多可能组成完整书册的数目。

输入输出样例

输入样例#1: 
5 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3
输出样例#1: 
2

说明

样例说明:

如题,N1=5,N2=3,N3=4,表示书有5本、练习册有3本、答案有4本。

M1=5,表示书和练习册共有5个可能的对应关系,分别为:书4和练习册3、书2和练习册2、书5和练习册2、书5和练习册1以及书5和练习册3。

M2=5,表示数和答案共有5个可能的对应关系,分别为:书1和答案3、书3和答案1、书2和答案2、书3和答案3以及书4和答案3。

所以,以上情况的话最多可以同时配成两个书册,分别为:书2+练习册2+答案2、书4+练习册3+答案3。

数据规模:

洛谷P1231 教辅的组成

对于数据点1, 2, 3,M1,M2<= 20

对于数据点4~10,M1,M2 <= 20000

首先想到了二分图最大匹配,结果匈牙利莫名其妙的炸了。。。

看了数据范围,发现匈牙利需要 O(n^2),故之。。。

改成网络流。

注意:

1.数组大小开10倍。

2.将每个书拆成两个点。

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 100010
#define MAX 999999999
using namespace std;
int n,m,k,s,t,c=2,ans=0;
int head[MAXN],deep[MAXN];
struct node{
int next,to,w;
}a[MAXN<<1];
inline int read(){
int date=0,w=1;char c=0;
while(c<='0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void add(int u,int v,int w){
a[c].to=v;a[c].w=w;
a[c].next=head[u];
head[u]=c++;
a[c].to=u;a[c].w=0;
a[c].next=head[v];
head[v]=c++;
}
bool bfs(){
int u,v;
queue<int> q;
memset(deep,0,sizeof(deep));
deep[s]=1;
q.push(s);
while(!q.empty()){
u=q.front();
q.pop();
for(int i=head[u];i;i=a[i].next){
v=a[i].to;
if(a[i].w&&!deep[v]){
deep[v]=deep[u]+1;
if(v==t)return true;
q.push(v);
}
}
}
return false;
}
int dfs(int x,int limit){
if(x==t)return limit;
int v,sum,cost=0;
for(int i=head[x];i;i=a[i].next){
v=a[i].to;
if(a[i].w&&deep[v]==deep[x]+1){
sum=dfs(v,min(limit-cost,a[i].w));
if(sum>0){
a[i].w-=sum;
a[i^1].w+=sum;
cost+=sum;
if(cost==limit)break;
}
else deep[v]=-1;
}
}
return cost;
}
int dinic(){
int ans=0;
while(bfs())
ans+=dfs(s,MAX);
return ans;
}
int main(){
int f,u,v;
n=read();m=read();k=read();
f=read();
for(int i=1;i<=f;i++){
u=read();v=read();
add(v,u+m,1);
}
f=read();
for(int i=1;i<=f;i++){
u=read();v=read();
add(u+n+m,v+n+n+m,1);
}
for(int i=1;i<=n;i++)add(i+m,i+n+m,1);
for(int i=1;i<=m;i++)add(n+m+k+n+1,i,1);
for(int i=1;i<=k;i++)add(i+n+n+m,n+m+k+n+2,1);
s=n+m+k+n+1;t=n+m+k+n+2;
printf("%d\n",dinic());
return 0;
}