C.Cheeeeen the Cute Cat

最大匹配

题目大意

给定一个具有 $2n2n$ 个节点的二部图，前 $nn$ 个节点和后 $nn$ 个节点各成一部

对于每对 $(i,j),i\mathrm{\ne }j(i,j),i\backslash ne\; j$ ，保证在 $i,j+ni,j+n$ 和 $j,i+nj,i+n$ 之间有且仅有一条边，整幅图的边数共 $C_n^{2}C\_n^2$ 条

求这个二部图的最大匹配

前置知识点

二分图

二分图最大匹配

解题思路

题解和讨论区谈及竞赛图的做法，以及相关的特点，稍微了解了一下但是赛事确实没发现可以把这个图转化成一个竞赛图//

当时一眼看去就像一道朴实无华的板子题，队友直接交了一发板子就过了//

跑一遍增广路求出最大匹配即可，具体的实现原理在OI-Wiki上有非常详细的推导与说明//

本蒟蒻就是看它学的qwq这里就不过多赘述了

参考代码

参考代码为已AC代码主干，其中部分功能需读者自行实现

最大匹配模板参考：二分图最大匹配-OI Wiki

void solve()
{
    ll n,t;
    cin >> n;
    augment_path G(n,n*2);
    FORLL(i,0,n-1)
        FORLL(j,0,n-1){
            cin >> t;
            if(t) G.add(i,j+n);
        }cout << G.solve() << endl;
}