网络流与dinic/Fulkerson模板以及相关题

对于一个二分图，我们想到如果将最大匹配转化为最大流就好了。
那么如何转化呢？对于一个匹配，一定是数条没有公共顶点的边，那么就想到了数条这样相同流的增广路
我们添加一个源点和汇点，它们分别向两边的两点各连一条容量为1，cost=0的边，这样就转化为了最大流来求这些边的问题了

#include 
#include 
#include 
#include 
#include 
#include 
//AC
using namespace std;

const int maxn=10000;
const int inf=0x3f3f3f3f;
int dis[maxn];
int cur[maxn];
int s,t,n,m,e;

struct edge
{
    int to,cap,rev;
};
vector g[maxn];

void addedge(int from,int to,int cap)
{
    g[from].push_back((edge){to,cap,g[to].size()});
    g[to].push_back((edge){from,0,g[from].size()-1});
}
//dinic
bool bfs(int st,int ed)
{
    memset(dis,inf,sizeof(dis));
    int q[maxn];
    int head=0;
    int tail=0;
    q[head]=st;
    dis[st]=0;
    while(head<=tail)
    {
        int h=q[head];
        head++;
        for(unsigned i=0;i0 && dis[e.to]==inf)
            {
                dis[e.to]=dis[h]+1;
                tail++;
                q[tail]=e.to;
            }
        }
    }
    return (dis[ed]!=inf);
}

int dfs(int v,int ed,int leftflow)
{
    if(leftflow==0 || v==ed)
    {
        return leftflow;
    }
    else
    {
        for(int &i=cur[v];i0 && dis[e.to]==dis[v]+1)/////
            {
                int f=dfs(e.to,ed,min(leftflow,e.cap));
                if(f>0)
                {
                    e.cap-=f;///////////////////
                    g[e.to][e.rev].cap+=f;///////////////
                    return f;
                }
            }
        }
        return 0;
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&e);
    s=0;
    t=n+m+1;
    memset(dis,inf,sizeof(dis));
    memset(cur,0,sizeof(cur));
    for(int i=0;i=1 && from<=n && to>=1 && to<=m)
        {
            to+=n;
            addedge(from,to,1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        addedge(s,i,1);
    }
    for(int j=n+1;j<=n+m;j++)
    {
        addedge(j,t,1);
    }
    int ans=0;
    while(bfs(s,t))
    {
        int f;
        memset(cur,0,sizeof(cur));/////////////
        while((f=dfs(s,t,inf))>0)
        {
            ans+=f;
        }
    }
    printf("%dn",ans);
    return 0;
}

给你10个冰球，你要运完，但是你要经过长度最小的道路
如何做呢？这里推荐一个用连续最短路的贝尔曼福德实现的算法：
流固定，每次以最短路增广，从流中减去对应流
这样写看上去比较好懂的

int min_cost_flow(int st,int ed,int f)
{
    int ans=0;
    while(f>0)
    {
        bool update=true;
        memset(dis,inf,sizeof(dis));
        dis[st]=0;
        while(update)
        {
            update=false;
            for(int i=0;i<=n+m+1;i++)
            {
                if(dis[i]!=inf)
                {
                    for(unsigned j=0;j0 && dis[e.to]>dis[i]+e.cost)
                        {
                            dis[e.to]=dis[i]+e.cost;
                            prevv[e.to]=i;
                            preve[e.to]=j;
                            update=true;
                        }
                    }
                }
            }
        }

        if(dis[ed]==inf)
        {
            return -1;
        }

        int d=inf;
        for(int i=ed;i!=st;i=prevv[i])
        {
            d=min(d,g[prevv[i]][preve[i]].cap);
        }

        f-=d;
        ans+=dis[ed]*d;
        for(int i=ed;i!=st;i=prevv[i])
        {
            edge & e=g[prevv[i]][preve[i]];
            e.cap-=d;
            g[i][e.rev].cap+=d;
        }
    }
    return ans;
}

应用当然不止这些 最主要是建模，这里有些题（书上的例题）
poj1273排水沟
poj3281奶牛的餐饮
poj3686玩具
luogu3386二分图匹配模板