【luogu1231】教辅的组成 [网络流 最大流]

luogu1231

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

三倍经验 另外两道我都是用匈牙利水过去的...

要注意把书拆点 因为有可能一本书用了多次

然后用dinic跑一遍dinic就好了！

#include<bits/stdc++.h>
using namespace std;
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)>(y)?(y):(x))
const int N=40000+5,M=2000000+5,inf=0x3f3f3f3f,P=19650827;
int n1,n2,n3,tt,m,s,t,maxflow=0;
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int head[N],tot=1;
struct edge{int v,flo,nxt;}e[M<<1];
void add(int u,int v,int flo){
    e[++tot]=(edge){v,flo,head[u]},head[u]=tot;
    e[++tot]=(edge){u,0,head[v]},head[v]=tot;
}

int d[N];
queue<int>q;
bool bfs(){
    memset(d,0,sizeof(d));
    while(!q.empty()) q.pop();
    q.push(s),d[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u],v;i;i=e[i].nxt)
        if(e[i].flo&&!d[(v=e[i].v)]){
            q.push(v),d[v]=d[u]+1;
            if(v==t) return 1;
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow,k;
    for(int i=head[x],v;i&&rest;i=e[i].nxt){
        if(e[i].flo&&d[v=e[i].v]==d[x]+1){
            k=dinic(v,Min(rest,e[i].flo));
            if(!k) d[v]=0;
            e[i].flo-=k,e[i^1].flo+=k,rest-=k;
        }
    } 
    return flow-rest;
} 


int main(){
    freopen("in2.txt","r",stdin);
//  freopen("DNA.out","w",stdout);
    rd(n1),rd(n2),rd(n3);tt=n1+n2+n3;
    rd(m);
    for(int i=1,x,y;i<=m;++i) rd(x),rd(y),add(y+n1,x,1);
    rd(m);
    for(int i=1,x,y;i<=m;++i) rd(x),rd(y),add(x+tt,y+tt-n3,1);
    s=tt+n1+1,t=s+1;
    for(int i=1;i<=n1;++i) add(i,i+tt,1);
    for(int i=1;i<=n2;++i) add(s,i+n1,1);
    for(int i=1;i<=n3;++i) add(i+tt-n3,t,1);
    int flow=0;
    while(bfs())
    while(flow=dinic(s,inf)) maxflow+=flow;
    printf("%d",maxflow);
    return 0;
}

【luogu1231】教辅的组成 [网络流 最大流]

原文：https://www.cnblogs.com/lxyyyy/p/11413380.html