网络流初学之网络流24题

当我只剩下最后一个Q题没AC的时候，我就知道，网络流这个坎我注定要迈出这一步 Marriage Match IV 在我博客已经写过题解 最短路配最大流
推荐一个生成图的网站Graph

网络流24题搭配飞行员
emmm 假象一个超级出水口(源点)和一个超级接水口(汇点) 我们把正飞行员连接在出水口，建里容量为1的边，反向建立一个容量为0的边（反悔）
把副飞行员连在汇点上 同源点类似的建图方式 ，最终再把题目给出的关系建图 跑一次Dinic就好了 最大流量就是我们能求到的最大匹配数

template <typename T>
void read(T &res) {
    bool flag = false;
    char ch;
    while (!isdigit(ch = getchar())) (ch == '-') && (flag = true);
    for (res = ch - 48; isdigit(ch = getchar()); res = (res << 1) + (res << 3) + ch - 48)
        ;
    flag && (res = -res);
}

const int N = 1e5 + 3, M = 5 * 1e6 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N];
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void in(Re &x) {
    int f = 0;
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9') f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    x = f ? -x : x;
}
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                 // bfs求源点到所有点的最短路
    for (Re i = 0; i <= n; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}

int main() {
    ll u, v;
    read(n);
    read(m);
    maxflow = 0;
    o = 1;
    for (int i = 1; i <= m; i++) {
        add(0, i, 1);
        add(i, 0, 0);
    }
    for (int i = m + 1; i <= n; i++) {
        add(i, n + 1, 1);
        add(n + 1, i, 0);
    }
    while (scanf("%lld %lld", &u, &v) != EOF) {
        if (u <= 0 || v <= 0) {
            break;
        }
        add(u, v, 1);
        add(v, u, 0);
    }
    st = 0;
    ed = n + 1;
    Dinic(st, ed);
    printf("%lld\n", maxflow);
    return 0;
}

---

• 接下来是漫长的懵逼时间 最大流最小割定理 （建议多看白书，博客）
  网络流24题 太空飞行计划&最大权闭合子图&&最大流最小割定理
• 
  S集合所连的顶点为做实验的项目，T集合所连的顶点为实验器材，那么如果S–T存在联通的路径，就说明当前状态是欠钱的，那么为了不欠钱我们就要使得S T集合不存在联通回路，那么我们就要开始割掉某些边使得S T不联通，那么我们要么割掉实验项目，要么割掉实验器材。 首先割掉实验项目会使得我们的收入减少，其次如果割掉器材，代表我们要买这个器材，也会使得我们 的收入减少，那么当前我们的总收入为Sum=Σ奖金 -(Σ不要的项目+器材) 简单的说就是使得上述割操作的花费最少我们的收益就最多 也就是利用最小割实现S T集合不联通并且删边的花费最少 根据最大流最小割定理，一个图的最大流等于最小割的值 那么我们用Dinic建图以后跑一次就OK了
• 最小割是一种思想 值等于最大流但是意义不等于最大流
• 理解理解，建图方式很直白但是要知道这是怎么来的（懵逼了很久）

#include<bits/stdc++.h>
#define il inline
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
const int N=1005,inf=233333333;
int n,m,s,t=520,dis[N],h[N],cnt=1,ans;
struct edge{
    int to,net,v;
}e[N*2];
il void add(int u,int v,int w)
{
    e[++cnt].to=v,e[cnt].net=h[u],e[cnt].v=w,h[u]=cnt;
    e[++cnt].to=u,e[cnt].net=h[v],e[cnt].v=0,h[v]=cnt;
}
il bool bfs()
{
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    q.push(s),dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].net)
        if(dis[e[i].to]==-1&&e[i].v>0)dis[e[i].to]=dis[u]+1,q.push(e[i].to);
    }
    return dis[t]!=-1;
}
il int dfs(int u,int op)
{
    if(u==t)return op;
    int flow=0,used=0;
    for(int i=h[u];i;i=e[i].net)
    {
        int v=e[i].to;
        if(dis[v]==dis[u]+1&&e[i].v>0)
        {
            used=dfs(v,min(e[i].v,op));
            if(!used)continue;
            flow+=used,op-=used;
            e[i].v-=used,e[i^1].v+=used;
            if(!op)break;
        }
    }
    if(!flow)dis[u]=-1;
    return flow;
}
int main()
{
    scanf("%d%d",&m,&n);
    int w,tot=0,x;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&w);tot+=w;
        add(s,i,w);
        while(getchar()==' '){scanf("%d",&x);add(i,x+m,inf);}
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&x),add(i+m,t,x);
    while(bfs())ans+=dfs(s,inf);
    ans=tot-ans;
    for(int i=1;i<=m;i++)if(dis[i]!=-1)printf("%d ",i);printf("\n");
    for(int i=1;i<=n;i++)if(dis[i+m]!=-1)printf("%d ",i);printf("\n");
    printf("%d",ans);
    return 0;
}

DAG最小路径覆盖不相交版本&&二分图最大匹配
先建立超级源点以及汇点，然后把V集合的点全部连上S 边容量为1 然后把每个V集合的点经行拆点 拆成 v–v^~ 将此问题转化为二分图求最大匹配问题，拆点后对应的点相互连接建立边容量为1，然后将拆出来的点连接上超级汇点，最终再输入题目的有向边信息，注意，我们要让u连接上与v对应的拆点，建立边容量为1 然后跑一次Dinic 一开始n个点独立，那么相当于有n条路径，我们每合并条，总路径数就会减少1，那么此DAG的最小路径覆盖数就等于了 n-maxflow 遍历1到n枚举对应的head数组 判断此时边容是否为0，为0则标记 （并查集思想，找祖先，输出路径）

template <typename T>
void read(T &res) {
    bool flag = false;
    char ch;
    while (!isdigit(ch = getchar())) (ch == '-') && (flag = true);
    for (res = ch - 48; isdigit(ch = getchar()); res = (res << 1) + (res << 3) + ch - 48)
        ;
    flag && (res = -res);
}

const int N = 1e5 + 3, M = 5 * 1e6 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N];
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                 // bfs求源点到所有点的最短路
    for (Re i = 0; i <=2*n+1; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}

int par[N], ru[N];
int norml(int x)
 {return (x - 1) % n + 1;}
void print_path(int st, int ed) {
    for(int i = 0; i <= n; ++i) par[i] = i;
    for(int i = 1; i <= n; ++i) {
        for(int v = head[i]; v!=0; v = a[v].next) {
            if(a[v].flow == 0 && a[v].to != st && a[v].to !=ed) {
                par[norml(i)] = norml(a[v].to);
                ++ru[par[norml(i)]];
            }
        }
    }
    for(int i = 1; i <= n; ++i) if(!ru[i]) {
        for(int v = i; ; v = par[v]) {
            printf(par[v] == v ? "%d\n" : "%d ", v);
            if(v == par[v]) break;
        }
    }
}
int main() {
  for(int i=0;i<=5000;i++){
    head[i]=0;
  }
   // ll u, v;
    read(n);
    read(m);
    maxflow = 0;
    o = 1;

    for(int i=1;i<=n;i++){
   add(0,i,1);
   add(i,0,0);
   add(i+n,2*n+1,1);
   add(2*n+1,i+n,0);
    }
     for(int i=1;i<=m;i++){
   ll uu,vv;
   read(uu);
   read(vv);
 add(uu,vv+n,1);
  add(vv+n,uu,0);
   }
    st = 0;
    ed =2* n + 1;
    Dinic(st, ed);
    print_path(st,ed);
    printf("%lld\n", n-maxflow);
    return 0;
}

HDU1045 经典二分图模型
一个棋盘，X代表墙，墙可以抵挡子弹，然后 。代表空位置，空位置我们可以放置炮塔，炮塔有四个攻击方向，它能够摧毁四个方向上的建筑物但是可以被墙体防御下来，现在问给了我们一个初始棋盘，能最多放多少个炮台而且炮台相互间不会摧毁对方 。
解法很多，可以爆搜，也可以整二分图，当然我是用最大流做的，二分图最大匹配转化为求最大流问题 我们先按行遍历棋盘 求出联通块 做上标记
同理再按列扫一次，然后把横向的联通块按标记号与超级源点相连建立边容量为1，同理把纵向的联通块按下标与超级汇点相连，接下来遍历标记数组如果当前位置是空的那么就把当前位置的横纵标记 相连（牵制作用）

template <typename T>
void read(T &res) {
    bool flag = false;
    char ch;
    while (!isdigit(ch = getchar())) (ch == '-') && (flag = true);
    for (res = ch - 48; isdigit(ch = getchar()); res = (res << 1) + (res << 3) + ch - 48)
        ;
    flag && (res = -res);
}

const int N = 1e5 + 3, M = 1e5 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N],op=0,oq=0;
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                 // bfs求源点到所有点的最短路
    for (Re i = 0; i <=op+oq+1; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}
char sf[6][6];
ll vix[6][6];
ll viy[6][6];
void cle(){
for(int i=0;i<=5000;i++){
head[i]=0;
}
memset(vix,0,sizeof(vix));
memset(viy,0,sizeof(viy));
memset(sf,'\0',sizeof(sf));
maxflow = 0;
o = 1;
   op=0,oq=0;
}
signed main(){

while(scanf("%lld",&n)!=EOF){
    if(n==0){
        break;
    }
cle();
  for(int i=1;i<=n;i++){
    scanf("%s",sf[i]+1);
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
     if(sf[i][j]=='.'){
    if(j==1||sf[i][j-1]=='X'){
    vix[i][j]=++op;

    }
     else{vix[i][j]=op;}
     }
    }
  }
   for(int j=1;j<=n;j++){
    for(int i=1;i<=n;i++){
    if(sf[i][j]=='.'){
    if(i==1||sf[i-1][j]=='X'){
    viy[i][j]=(++oq)+op;
    }
    else{
    viy[i][j]=op+oq;
    }
    }
    }
  }
st=0;
ed=op+oq+1;
  for(int i=1;i<=op;i++){
   add(st,i,1);
   add(i,st,0);
  }
  for(int i=1;i<=oq;i++){
    add(i+op,ed,1);
   add(ed,i+op,0);
  }
 for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    if(sf[i][j]=='X'){
            continue;
    }
  add(vix[i][j],viy[i][j],1);
    add(viy[i][j],vix[i][j],0);
    }
 }
Dinic(st, ed);
    printf("%lld\n", maxflow);
}
    return 0;
}

emmm 说实话题意感觉有点讲的不太明白，大概猜到了就是判断是不是二分图，如果是就求出它的最大匹配数 代码写的太丑了 用的Dinic
判断二分图用染色法 - - 具体的自己学学

#include <bits/stdc++.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x & (-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define Re register int
using namespace std;
ll gcd(ll a, ll b) {
    if (a < 0)
        a = -a;
    if (b < 0)
        b = -b;
    return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
void read(T &res) {
    bool flag = false;
    char ch;
    while (!isdigit(ch = getchar())) (ch == '-') && (flag = true);
    for (res = ch - 48; isdigit(ch = getchar()); res = (res << 1) + (res << 3) + ch - 48)
        ;
    flag && (res = -res);
}

const int N = 1e5 + 3, M = 1e5 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N],op=0,oq=0;
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                 // bfs求源点到所有点的最短路
    for (Re i = 0; i <=2*n+1; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}

const int manx=1e5+5;
const int mamx=1e5+5;
ll headp[manx];
ll vis[manx];
ll k=1;
struct node{
    ll v,next,w;
}aa[mamx];
void addp(ll u,ll v,ll w)
{
    aa[++k].next=headp[u];
    aa[k].w=w;
    aa[k].v=v;
    headp[u]=k;
}


bool judge()
{
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(1);
    vis[1]=1;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=headp[now];i!=0;i=aa[i].next)
        {
            int nex=aa[i].v;
            if(!vis[nex])
            {
                q.push(nex);
                vis[nex]=-vis[now];
            }
            if(vis[nex]==vis[now]) return false;//不是二分图
        }
    }
    return true;
}

ll cnm[manx];
ll rnm[manx];
void cle(){
for(int i=0;i<=500;i++){
head[i]=0;
headp[i]=0;
}
maxflow = 0;
o = 1;
k=1;
}
signed main(){
while(scanf("%lld%lld",&n,&m)!=EOF){
cle();
for(int i=1;i<=m;i++){
   read(rnm[i]);
   read(cnm[i]);
   addp(rnm[i],cnm[i],1);
}
if(!judge()){
    printf("No\n");
   continue;
}
for(int i=1;i<=n;i++){
    add(0,i,1);
    add(i,0,0);
    add(i+n,2*n+1,1);
    add(2*n+1,i+n,0);
}
for(int i=1;i<=m;i++){
    add(rnm[i],cnm[i]+n,1);
      add(cnm[i]+n,rnm[i],0);
}
st=0;
ed=2*n+1;
Dinic(st,ed);
printf("%lld\n",maxflow);
    }
    return 0;
}

老样子用的Dinic算法，首先想想课程与学生的关系，显然我们要通过学生来决定课程的人流量，那么就很简单了，用学生与S建边，用课程与T建边再按照课程学生对应关系建立边容量为1的二分图，求最大流 搞定

#include <bits/stdc++.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x & (-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define Re register int
using namespace std;
 ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}



const int N = 1e5 + 3, M = 1e6 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N];
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void in(Re &x) {
    int f = 0;
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9') f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    x = f ? -x : x;
}
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                 // bfs求源点到所有点的最短路
    for (Re i = 0; i <= n+m+1; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}

void cle(){
for(int i=0;i<=1000;i++){
    head[i]=0;
}
o=1;
maxflow=0;
}
signed main() {
    ll t;
    read(t);
    while(t--){
    cle();

    read(n); //课程
    read(m); // 学生
    maxflow = 0;
    for(int i=1;i<=m;i++){
    add(0,i,1);
    add(i,0,0); // 连学生
    }
   for(int i=1;i<=n;i++){
   add(i+m,n+m+1,1);
   add(n+m+1,m+i,0);
   }
  for(int i=1;i<=n;i++){
   ll px;
   read(px); //课
   for(int j=1;j<=px;j++){
    ll stu;
    read(stu);
    add(stu,i+m,1);
    add(i+m,stu,0);
   }
  }
   // o = 1;
    st = 0;
    ed = n + 1+m;
    Dinic(st, ed);
    //printf("%lld\n", maxflow);
    if(maxflow!=n){
        printf("NO\n");
    }
    else{
        printf("YES\n");
    }
    }
    return 0;
}

HDU1281 Dinic&&匈牙利算法
哎，这个题要边枚举边删除边还原于是我学了（套板子）匈牙利算法 简单的讲这个题就是以x y 作为二分图先求一次最大匹配然后我们再枚举那k个坐标，删除它，如果此时最大匹配数小于max 那么说明这个位置是关键位置 那么我们ans++ 还有一种Dinic写法 每次推掉重新建图

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
const int INF = 2e9;
const int MOD = 1e9+7;
const int MAXN = 100+10;

int n, uN, vN;
int M[MAXN][MAXN], link[MAXN];
bool vis[MAXN];

bool dfs(int u)
{
    for(int i = 1; i<=vN; i++)
    if(M[u][i] && !vis[i])
    {
        vis[i] = true;
        if(link[i]==-1 || dfs(link[i]))
        {
            link[i] = u;
            return true;
        }
    }
    return false;
}

int hungary()
{
    int ret = 0;
    memset(link, -1, sizeof(link));
    for(int i = 1; i<=uN; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ret++;
    }
    return ret;
}

int main()
{
    int k, kase = 0;
    while(scanf("%d%d%d", &uN, &vN, &k)!=EOF)
    {
        memset(M, false, sizeof(M));
        for(int i = 1; i<=k; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            M[x][y] = true;
        }
        int cnt = hungary();  //匈牙利
        int ans = 0;
        for(int i = 1; i<=uN; i++)
        for(int j = 1; j<=vN; j++)
        {
            if(!M[i][j]) continue;
            M[i][j] = false;
            if(hungary()<cnt) ans++;
            M[i][j] = true;
        }
  printf("Board %d have %d important blanks for %d chessmen.\n", ++kase, ans, cnt);
    }
}

#include <bits/stdc++.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x & (-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define Re register int
using namespace std;
 ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}



const int N = 1e5 + 3, M = 1e6 + 3;
int x, y, z, o = 1, n, m, h, t, st, ed, Q[N], cur[N], dis[N], head[N];
long long maxflow;
struct QAQ {
    int to, next, flow;
} a[M << 1];
inline void in(Re &x) {
    int f = 0;
    x = 0;
    char c = getchar();
    while (c < '0' || c > '9') f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    x = f ? -x : x;
}
inline void add(Re x, Re y, Re z) { a[++o].flow = z, a[o].to = y, a[o].next = head[x], head[x] = o; }
inline int bfs(Re st, Re ed) {                                 // bfs求源点到所有点的最短路
    for (Re i = 0; i <= n+m+1; ++i) cur[i] = head[i], dis[i] = 0;  //当前弧优化cur=head
    h = 1, t = 0, dis[st] = 1, Q[++t] = st;
    while (h <= t) {
        Re x = Q[h++], to;
        for (Re i = head[x]; i; i = a[i].next)
            if (a[i].flow && !dis[to = a[i].to]) {
                dis[to] = dis[x] + 1, Q[++t] = to;
                if (to == ed)
                    return 1;
            }
    }
    return 0;
}
inline int dfs(Re x, Re flow) {  // flow为剩下可用的流量
    if (!flow || x == ed)
        return flow;  //发现没有流了或者到达终点即可返回
    Re tmp = 0, to, f;
    for (Re i = cur[x]; i; i = a[i].next) {
        cur[x] = i;  //当前弧优化cur=i
        if (dis[to = a[i].to] == dis[x] + 1 && (f = dfs(to, min(flow - tmp, a[i].flow)))) {
            //若边权为0，不满足增广路性质，或者跑下去无法到达汇点，dfs返回值f都为0，不必执行下面了
            a[i].flow -= f, a[i ^ 1].flow += f;
            tmp += f;  //记录终点已经从x这里获得了多少流
            if (!(flow - tmp))
                break;
            // 1. 从st出来流到x的所有流被榨干。后面的边都不用管了，break掉。
            //而此时边i很可能还没有被榨干，所以cur[x]即为i。
            // 2. 下面儿子的容量先被榨干。不会break，但边i成了废边。
            //于是开始榨x的下一条边i'，同时cur[x]被更新成下一条边i'
            //直至榨干从x上面送下来的水流结束（即情况1）。
        }
    }
    return tmp;
}
inline void Dinic(Re st, Re ed) {
    Re flow = 0;
    while (bfs(st, ed)) maxflow += dfs(st, inf);
}
ll rnm[5000],k;
ll cnm[5000];
void cle(){
for(int i=0;i<=1000;i++){
    head[i]=0;
}
o=1;
maxflow=0;
}
void fac(ll csu){
for(int i=0;i<=1000;i++){
head[i]=0;
}
o=1;
maxflow=0;
 for(int i=1;i<=n;i++){
    add(0,i,1);
    add(i,0,0); //建立X
   }
   for(int i=1;i<=m;i++){
    add(n+i,n+m+1,1);
    add(n+m+1,n+i,0); //建立Y
   }
 for(int i=1;i<=k;i++){
   // ll rnm,cnm;
   if(i==csu){
    continue;
   }
    add(rnm[i],cnm[i]+n,1);
    add(cnm[i]+n,rnm[i],0);
   }
}


signed main() {

   ll ca=0;
    while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF){
    cle();
    ca++;
    ll fuck;
   for(int i=1;i<=n;i++){
    add(0,i,1);
    add(i,0,0); //建立X
   }
   for(int i=1;i<=m;i++){
    add(n+i,n+m+1,1);
    add(n+m+1,n+i,0); //建立Y
   }
   for(int i=1;i<=k;i++){
    read(rnm[i]);
    read(cnm[i]);
    add(rnm[i],cnm[i]+n,1);
    add(cnm[i]+n,rnm[i],0);
   }
   ll akk=0;
   st=0;
   ed=n+m+1;
   Dinic(st,ed);
   fuck=maxflow;
   for(int i=1;i<=k;i++){
    fac(i);
    Dinic(st,ed);
    if(maxflow<fuck){
        akk++;
    }
   }
  printf("Board %lld have %lld important blanks for %lld chessmen.\n",ca,akk,fuck);

}
    return 0;
}祖安编程

二分图匹配&&记录过程
摊牌了，我是弟弟，这个题Dinic不会写 写的匈牙利暴力
如果最大匹配数等于n 那么说明此题有解 然后遍历一次标记数组

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
const int INF = 2e9;
const int MOD = 1e9+7;
const int MAXN = 1000+10;

int n, uN, vN;
int M[MAXN][MAXN], link[MAXN];
bool vis[MAXN];

bool dfs(int u)
{
    for(int i = 1; i<=uN; i++)
    if(M[u][i] && !vis[i])
    {
        vis[i] = true;
        if(link[i]==-1 || dfs(link[i]))
        {
            link[i] = u;
            return true;
        }
    }
    return false;
}

int hungary()
{
    int ret = 0;
    memset(link, -1, sizeof(link));
    for(int i = 1; i<=uN; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i))
            ret++;
    }
    return ret;
}
int rnm[5555];
int cnm[5555];
int main()
{
    int k, kase = 0;
    while(scanf("%d", &uN)!=EOF)
    {
        int rt=0;
        memset(M, false, sizeof(M));
        for(int i = 1; i<=uN; i++)
        {
            for(int j=1; j<=uN; j++)
            {
                // int x, y;
                int x;
                scanf("%d",&x);
                if(x==1)
                {
                    M[i][j] = true;
                }
            }
        }
        int cnt = hungary();

        //  printf("Q %d\n",cnt);
        if(cnt<uN)
        {
            printf("-1\n");
            continue;
        }
        for(int i=1; i<=uN; i++)
        {
            if(link[i]!=i)
            {
                for(int j=i+1; j<=uN; j++)
                {
                    if(link[j]==i)
                    {
                        rnm[++rt]=i;
                        cnm[rt]=j;
                        swap(link[i],link[j]);
                    }
                }
            }
        }
        printf("%d\n",rt);
        for(int i=1; i<=rt; i++)
        {
            printf("C %d %d\n",rnm[i],cnm[i]);
        }
    }
}

今天就到这里吧，感谢从容大佬对我的帮助，i了i了 %%% box
学网络流学着学着来刷二分图匹配了 QAQ明天继续肝

本文地址：https://blog.csdn.net/weixin_45948940/article/details/107496689

如对本文有疑问， 点击进行留言回复！！