P1231 教辅的组成

三类物品并非三维匹配，而是中间层容量

问题

P1231 教辅的组成
每套教辅由一本书、一份练习册和一份答案组成。书与练习册、书与答案分别存在允许搭配关系，每件物品都只能使用一次，要求最多组成多少套完整教辅。

数据规模：三类物品数量均不超过 $10^4$，两类允许关系边数均不超过 $2\times10^4$。

表面上有三类对象：“书”，“练习册”，“答案”；同时存在两种关系 “书与练习册”，“书与答案”。

发现三类对象的两种关系都有同一个中心 —— "书"，所以一套完整的教辅，实际上是寻找 “练习册 $\to$ 书 $\to$ 答案” 的组合，所以自然会想到建立三层流网络。

练习册和答案分别安排在网络的两端，让源点到每份练习册、每份答案到汇点的容量都设为 $1$，从而保证它们至多使用一次。不过问题卡在中间的书上：如何保证每本书在整个方案中至多被使用一次？

拆点

普通流网络中的节点本身没有容量，即使设置所有进入和离开某本书的关系边容量都设置为 $1$，仍然可能有多单位流同时经过这个节点。

示例

例如同一本书 $B$ 可以搭配练习册 $A_1,A_2$，也可以搭配答案 $C_1,C_2$。如果直接建立普通三层图，就可能同时存在 $A_1\to B\to C_1$ 与 $A_2\to B\to C_2$ 两单位流，相当于同一本书组成了两套教辅。

所以我们需要限制书本这个对象总共只能使用一次，把每本书拆成两个点 $B_{in}$ 和 $B_{out}$，并在两者之间连接容量为 $1$ 的边，这样所有经过这本书的流都必须穿过同一条拆点边。

网络最终形成 $S\to$ 练习册 $\to B_{in}\to B_{out}\to$ 答案 $\to T$ 的结构。两侧关系边负责表达兼容关系，书的拆点边则负责限制书本的使用次数。

注1：本题拆点的意义是给节点加入容量限制，把“点的总使用次数”转化为一条边的容量限制。

注2：虽然题目出现三类对象，但合法性并不依赖整个三元组 $(a,b,c)$ 的额外关系。练习册和答案只需要分别与同一本书兼容，因此两个局部关系可以通过“书”这个中心节点连接起来；若合法性真正依赖任意三元组整体，就不能用这一层节点容量直接表达。

▶

P1231 建图

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

void solve( ) {
    int n1 = read( ), n2 = read( ), n3 = read( );

    int tot = 0;
    vector<int> a( n2 + 1 );
    vector<int> bi( n1 + 1 );
    vector<int> bo( n1 + 1 );
    vector<int> c( n3 + 1 );

    for( int i = 1; i <= n2; ++ i ) a[i] = ++ tot;
    for( int i = 1; i <= n1; ++ i ) bi[i] = ++ tot;
    for( int i = 1; i <= n1; ++ i ) bo[i] = ++ tot;
    for( int i = 1; i <= n3; ++ i ) c[i] = ++ tot;

    int S = ++ tot, T = ++ tot;
    init( T );

    for( int i = 1; i <= n2; ++ i ) {
        add_edge( S, a[i], 1 );
    }

    for( int i = 1; i <= n1; ++ i ) {
        add_edge( bi[i], bo[i], 1 );
    }

    for( int i = 1; i <= n3; ++ i ) {
        add_edge( c[i], T, 1 );
    }

    int m1 = read( );
    for( int i = 1; i <= m1; ++ i ) {
        int u = read( ), v = read( );
        add_edge( a[v], bi[u], 1 );
    }

    int m2 = read( );
    for( int i = 1; i <= m2; ++ i ) {
        int u = read( ), v = read( );
        add_edge( bo[u], c[v], 1 );
    }

    ll mxflow = Dinic( S, T, T );
    cout << mxflow << '\n';
}