洛谷1231 教辅的组成

洛谷1231 教辅的组成

https://www.luogu.org/problem/show?pid=1231

题目背景

滚粗了的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。

数据规模:

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

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

拆点+最大流

为什么要拆点?

以为一般的最大流可一个点经过多次,而本题一个点只能经过1次,所以要拆成一个流量为1的边

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10000
#define M 20001
using namespace std;
int n1,n2,n3,m1,m2,tot=1,src,dec,ans,cur[N*5],lev[N*5],head,tail,que[4*5*N],tmp;
int front[N*5];
struct node
{
    int to,next,cap;
}e[M*10];
inline void add(int u,int v)
{
    e[++tot].to=v;e[tot].next=front[u];e[tot].cap=1;front[u]=tot;
    e[++tot].to=u;e[tot].next=front[v];e[tot].cap=0;front[v]=tot;
}
inline bool bfs()
{
    for(int i=0;i<=N*5;i++) {lev[i]=-1;cur[i]=front[i];}
    head=tail=0;
    que[tail++]=src;lev[src]=0;
    while(head<tail)
    {
        int now=que[head];
        for(int i=front[now];i;i=e[i].next)
        {
            int to=e[i].to;
            if(e[i].cap>0&&lev[to]==-1)
            {
                lev[to]=lev[now]+1;
                que[tail++]=to;
                if(to==dec) return true;
            }
        }
        head++;
    }
    return false;
}
inline int dinic(int now,int flow)
{
    if(now==dec) return flow;
    int res=0,delta;
    for(int & i=cur[now];i;i=e[i].next)
    {
        int to=e[i].to;
        if(e[i].cap>0&&lev[to]>lev[now])
         {
             delta=dinic(to,min(e[i].cap,flow-res));
            if(delta)
            {
                e[i].cap-=delta;e[i^1].cap+=delta;
                res+=delta;if(res==flow) break;
            }
         }
    }
    if(res!=flow) lev[now]=-1;
    return res;
}
int main()
{
    scanf("%d%d%d",&n1,&n2,&n3);
    src=0;dec=4*N+1;
    for(int i=1;i<=n3;i++) add(src,i);
    for(int i=1;i<=n1;i++) add(N+i,N*2+i);
    for(int i=1;i<=n2;i++)
     add(i+3*N,dec);
    int x,y;
    scanf("%d",&m1);
    for(int i=1;i<=m1;i++)
    {
        scanf("%d%d",&x,&y);
        add(x+2*N,y+3*N);
    }
    scanf("%d",&m2);
    for(int i=1;i<=m2;i++)
    {
        scanf("%d%d",&x,&y);
        add(y,x+N);
    }
    while(bfs())
     ans+=dinic(src,n3);
    printf("%d",ans);
}

bfs中去掉if(to==des) reurn true

改为在最后return钱加一个 if(lev[dec]!=-1) return true;

前者比后者快。

原因:因为是bfs

时间: 02-22

洛谷1231 教辅的组成的相关文章

洛谷——P1231 教辅的组成

P1231 教辅的组成 题目背景 滚粗了的HansBug在收拾旧语文书,然而他发现了什么奇妙的东西. 题目描述 蒟蒻HansBug在一本语文书里面发现了一本答案,然而他却明明记得这书应该还包含一份练习题.然而出现在他眼前的书多得数不胜数,其中有书,有答案,有练习册.已知一个完整的书册均应该包含且仅包含一本书.一本练习册和一份答案,然而现在全都乱做了一团.许多书上面的字迹都已经模糊了,然而HansBug还是可以大致判断这是一本书还是练习册或答案,并且能够大致知道一本书和答案以及一本书和练习册的对应

洛谷 P2709 BZOJ 3781 小B的询问

题目描述 小B有一个序列,包含N个1~K之间的整数.他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数.小B请你帮助他回答询问. 输入输出格式 输入格式: 第一行,三个整数N.M.K. 第二行,N个整数,表示小B的序列. 接下来的M行,每行两个整数L.R. 输出格式: M行,每行一个整数,其中第i行的整数表示第i个询问的答案. 输入输出样例 输入样例#1: 6 4 3 1 3 2 1 1 3

洛谷教主花园dp

洛谷-教主的花园-动态规划 题目描述 教主有着一个环形的花园,他想在花园周围均匀地种上n棵树,但是教主花园的土壤很特别,每个位置适合种的树都不一样,一些树可能会因为不适合这个位置的土壤而损失观赏价值. 教主最喜欢3种树,这3种树的高度分别为10,20,30.教主希望这一圈树种得有层次感,所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低,并且在此条件下,教主想要你设计出一套方案,使得观赏价值之和最高. 输入输出格式 输入格式: 输入文件garden.in的第1行为一个正整数n,表示需要种的

洛谷 P2801 教主的魔法 题解

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置. 题目链接:https://www.luogu.org/problem/show?pid=2801 题目描述 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息组每个英雄看.于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1.2.…….N. 每个人的身高一开始都是不超过1000的正整数.教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W.(虽然L=R时并不

洛谷P1466 集合 Subset Sums

洛谷P1466 集合 Subset Sums这题可以看成是背包问题 用空间为 1--n 的物品恰好填充总空间一半的空间 有几种方案 01 背包问题 1.注意因为两个交换一下算同一种方案,所以最终 要 f [ v ] / 2 2.要开 long long 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string&g

洛谷P1160 队列安排 链表

洛谷P1160 队列安排   链表 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <string> 6 #include <algorithm> 7 #include <iomanip> 8 #include <iostream> 9 using namespace std

洛谷 P3367 并查集模板

#include<cstdio> using namespace std; int n,m,p; int father[2000001]; int find(int x) { if(father[x]!=x) father[x]=find(father[x]); return father[x]; } void unionn(int i,int j) { father[j]=i; } int main() { scanf("%d%d",&n,&m); for

[题解]洛谷比赛『期末考后的休闲比赛2』

[前言] 这场比赛已经结束了有几天,但我各种忙,虽然AK但还是没来得及写题解.(我才不会告诉你我跑去学数据结构了) T1 区间方差 (就不贴题好了) 首先可以推公式(我们可以知道,线段树然而并不能通过初中学过的方差公式在log(L)内求出方差): (s2表示方差,L表示区间长度,xi表示区间的每一项,最后一个x上画了一根线表示这些数据的平均数) 用二项式定理完全平方公式可得: 再次展开: 另外,再代入以下这个 得到了: 然后继续吧.. 然后duang地一声合并同类项,于是我们得到了: 然后可以高

洛谷P1471 方差

蒟蒻HansBug在一本数学书里面发现了一个神奇的数列,包含N个实数.他想算算这个数列的平均数和方差. ——by 洛谷; http://www.luogu.org/problem/show?pid=1471 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<