二分图常见套路：

1，（二分图）匹配图枚举匹配方案时，枚举<idx的偶数边，判断在残留网中容量是否为空即可
2，获得一条边的两个点使用成对变换的点
3，匹配图中枚举某个点的匹配对象时判断：点的编号是否在带匹配界内，容量
4，输出可行方案时记得减去为了匹配而制造的偏移量
5，判断最大流是不是满流需要一个tot积累所有的指出边的流量，并和Dinic判断

T1

题目

二分图最大匹配并输出方案

友好链接

https://www.luogu.com.cn/problem/P2756

code

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

int main()
{
    scanf("%d%d", &m, &n);
    memset(h, -1, sizeof h);
    s=0;
    t=n+1;
    int a, b;

    while (cin>>a>>b,a!=-1&&b!=-1)
    {
        add(a, b, 1);
    }

    rep(i,1,m)add(s,i,1);
    rep(i,m+1,t-1) add(i,t,1);


    printf("%d\n", Dinic());

    for (int i = 0; i < idx; i += 2)
        if (e[i] > m && e[i] <= n && !f[i])
            printf("%d %d\n", e[i ^ 1], e[i]);


    return 0;
}

T2

题目

二分图多重匹配并出方案

友好链接

https://www.acwing.com/problem/content/2181/

code

int main()
{
    cin>>m>>n;
    memset(h, -1, sizeof h);
    s=0;
    t=n+1+m;
    int tot= 0;
    rep(i,1,m)
    {
        int x;
        cin>>x;
        tot+=x;
        add(s,i,x);
    }

    rep(i,m+1,t-1)
    {
        int c;
        scanf("%d", &c);
        add(i, t, c);
    }

    rep(i,1,m)
        rep(j,m+1,t-1)
            add(i, j, 1);

    if (Dinic() != tot) puts("0");

    else
    {
        puts("1");
        rep(i,1,m)
        {
            for (int j = h[i]; ~j; j = ne[j])
                if (e[j] > m && e[j] <= m + n && !f[j])
                    printf("%d ", e[j] - m);
            puts("");
        }
    }

    return 0;
}