網(wǎng)絡(luò)流與dinic/Fulkerson模板以及相關(guān)題

對于一個二分圖，我們想到如果將最大匹配轉(zhuǎn)化為最大流就好了。
那么如何轉(zhuǎn)化呢？對于一個匹配，一定是數(shù)條沒有公共頂點的邊，那么就想到了數(shù)條這樣相同流的增廣路
我們添加一個源點和匯點，它們分別向兩邊的兩點各連一條容量為1，cost=0的邊，這樣就轉(zhuǎn)化為了最大流來求這些邊的問題了

#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個冰球，你要運完，但是你要經(jīng)過長度最小的道路
如何做呢？這里推薦一個用連續(xù)最短路的貝爾曼福德實現(xiàn)的算法：
流固定，每次以最短路增廣，從流中減去對應(yīng)流
這樣寫看上去比較好懂的

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;
}

應(yīng)用當(dāng)然不止這些 最主要是建模，這里有些題（書上的例題）
poj1273排水溝
poj3281奶牛的餐飲
poj3686玩具
luogu3386二分圖匹配模板