【解题报告】洛谷 P1231 教辅的组成

题目链接
CSDN链接
这道题就只是一道普通的最大流问题，但是关键所在就是如何构图。要不是我看了题解，真的想不到这个构图方法呢
题目大意我就不写了，自己看好了。因为我觉得我写得可能还不如你们直接看题目的好

我疑惑的地方

我还没有做过这种有多种搭配的问题，所以我刚开始的构图思路就是：

1. 从源点S向所有的书连一条边
2. 从书向相关的答案和练习册连一条边
3. 从答案和练习册向汇点T连一条边

但是，这么做显然是不对的。

正确的方法

1. 把所有的书拆成两个点，我称之为book~start~和book~end~
2. 从源点S向每一本练习册连一条边，容量为1，表示这本练习册最多只能选一次
3. 若练习册u和书v是对应的，从练习册u向v~start~连一条容量为1的边，（事实上这里的容量只要大于等于1就可以）表示u和v是对应的。
4. 把每一本书的book~start~向book~end~连一条容量为一的边，这样就可以限制流过一本书的流量最多为1，表示每一本书最多只能被选一遍。
5. 若书u和答案v是对应的，从书u~end~向v连一条容量为1的边，（事实上这里也是容量大于等于1就可以了，因为流过book~end~这个点的流量最多只能是1）表示u和v是对应的
6. 所有的答案向汇点连一条容量为1的边，表示这本答案只能被选一次

7. 这张图的最大流即为答案所求
   图片示意大致如下

   感悟

   又学会了一种构图方法。但是如果不是只有三类物品，而是有四类或者更多物品的话，我就不知道怎么构图了。

   AC代码

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int INF=100000000;
const int N=50000;
const int M=150000;
int Head[N],Next[M],Edge[M],Ver[M],tot=1;
int D[N];
const int S=40001,T=40002;
void add(int,int,int);
int min(int,int);
int max(int,int);
bool bfs(void);
int dinic(int,int);//我用dinic算法求最大流 
int main()
{
    //我用Head[1~10000]存book_start
    //    Head[10001~20000]存练习册 
    //    Head[20001~30000]存答案
    //    Head[30001~40000]存book_end
    //不要问我为什么这么存，我也是随便来的 
    int n1,n2,n3,m1,m2;
    scanf("%d%d%d",&n1,&n2,&n3);
    for(int i=1;i<=n2;i++)
        add(S,10000+i,1);
    for(int i=1;i<=n3;i++)
        add(20000+i,T,1);
    for(int i=1;i<=n1;i++)
        add(i,30000+i,1);
    scanf("%d",&m1);
    for(int i=1;i<=m1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(10000+y,x,1);
    }
    scanf("%d",&m2);
    for(int i=1;i<=m2;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(30000+x,20000+y,1);
    }
    int max_flow=0;
    while(bfs()) max_flow+=dinic(S,INF);
    printf("%d\n",max_flow);
    return 0;
}
int dinic(int x,int flow)
{
    if(x==T) return flow;
    int rest=flow;
    for(int p=Head[x];rest&&p;p=Next[p])
    {
        if(D[Ver[p]]==D[x]+1&&Edge[p])
        {
            int k=dinic(Ver[p],min(rest,Edge[p]));
            if(!k) D[Ver[p]]=0;
            Edge[p]-=k;
            Edge[p^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
bool bfs(void)
{
    memset(D,0,sizeof(D));
    D[S]=1;
    queue <int> q;
    q.push(S);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int p=Head[x];p;p=Next[p])
            if(!D[Ver[p]]&&Edge[p])
            {
                D[Ver[p]]=D[x]+1;
                if(Ver[p]==T) return 1;
                q.push(Ver[p]);
            }
    }
    return 0;
}
void add(int u,int v,int c)
{
    Next[++tot]=Head[u],Head[u]=tot,Edge[tot]=c,Ver[tot]=v;
    Next[++tot]=Head[v],Head[v]=tot,Edge[tot]=0,Ver[tot]=u;
}
inline int max(int a,int b)
{
    return a>b?a:b;
}
inline int min(int a,int b)
{
    return a<b?a:b;
}

【解题报告】洛谷 P1231 教辅的组成

原文：https://www.cnblogs.com/Frank-FFF/p/10123754.html