Dinic算法实现二分图匹配

在学习匈牙利算法的时候便知道网络流可以以更小的时间复杂度解决同样的问题
近期学了网络流，刚好可以再来玩儿玩儿二分图

其实Dinic算法在解决二分图匹配的时候和普通的网络流题目并没有太大区别，主要就是建图
此时，你肯定想打我，因为网络流大部分都是考建图（逃
具体说一下对于二分图这种特殊的图应该怎么建图（捂脸

给一张二分图，一个集合X中含有n个元素，另一个集合Y中含有m个元素

首先，把二分图中互相连接的点连接起来，设权值为1。恩，这一步可以看做翻译题目;
然后，找到一个超级源点和一个超级汇点。通常前者找0，后者找n+m+1;
最后，将X中的元素都与超级源点连起来，Y中的元素都和超级汇点连起来。这些边的权值都为1;

建图完成，搞定收工（雾

从超级源点到超级汇点跑一波Dinic，最大匹配就素最大流啦！
至于证明，显然可得嘛！（划掉）网上草鸡多证明的，自己百度啦~
毕竟，我不在意那些细节所以我不会。不服你打我啊~~

来一道很简单的题目，先说匈牙利算法是可以AC滴~~~

【rqnoj140】寻找代表元

题目描述
温中一共有n个社团，分别用1到n编号。
温中一共有m个人，分别用1到m编号。每个人可以参加一个或多个社团，也可以不参加任何社团。
每个社团都需要选一个代表。我们希望更多的人能够成为代表。

输入格式
第一行输入两个数n和m。以下n行每行若干个数，这些数都是不超过m的正整数。其中第i行的数表示社团i的全部成员。每行用一个0结束。

输出格式
输出最多的能够成为代表的人数。

数据范围
n,m<=200

样例输入
4 4
1 2 0
1 2 0
1 2 0
1 2 3 4 0

样例输出
3

唔，裸题不想解释太多了。给你个眼神自己做！

#include
#include
#include
#include
#define INF 1e8
using namespace std;
const int maxn=1005;
struct Edge{int from,to,cap,flow;};
int n,m,s,t,k,x;
vectoredges;
vector<int>G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];
void AddEdge(int from,int to,int cap){
    edges.push_back((Edge){from,to,cap,0});
    edges.push_back((Edge){to,from,0,0});
    k=edges.size();
    G[from].push_back(k-2);
    G[to].push_back(k-1);
}
bool BFS(){
    memset(vis,0,sizeof(vis));
    queue<int>Q;
    Q.push(s);
    d[s]=0;
    vis[s]=true;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=0;i            Edge& e=edges[G[x][i]];
            if(!vis[e.to] && e.cap>e.flow){
                vis[e.to]=true;
                d[e.to]=d[x]+1;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}
int DFS(int x,int a){
    if(x==t || a==0) return a;
    int flow=0,f;
    for(int &i=cur[x];i        Edge& e=edges[G[x][i]];
        if(d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0){
            e.flow+=f;
            edges[G[x][i]^1].flow-=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}
int MaxFlow(int s,int t){
    int flow=0;
    while(BFS()){
        memset(cur,0,sizeof(cur));
        flow+=DFS(s,INF);
    }
    return flow;
}
int main(){
    scanf("%d%d",&n,&m);
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        while(x!=0){AddEdge(i,x+n,1);scanf("%d",&x);}
    }
    for(int i=1;i<=n;i++)
        AddEdge(s,i,1);
    for(int i=1;i<=m;i++)
        AddEdge(i+n,t,1);
    printf("%d\n",MaxFlow(s,t));
    return 0;
}

PS：二分图匹配的题都可以用这种方法去操一下。
毕竟匈牙利能做的Dinic也能，Dinic能做的匈牙利不一定能。

————
菜鸡我发现当年写错了个地方qwq