引子

网络流的题目大概在半年前就开始做了,然而题解却一直拖欠着没写,我会在以后(如果有空?)一一补上 网络流问题主要包括最大流,费用流等等,算法很多,这些我用的主要就是蓝书里的Dinic和ISAP,欢迎来看。

T1 飞行员配对方案

题解

二分图最大匹配。设X集合与Y集合,中间连一条流为1的边,另建立一个超级源S和超级汇T,S与X集连一条流为1的有向边,Y集与T同样连一条流为1的有向边,最后跑一边Dinic,最大流即为最大匹配数,而最小割则是其对应方案。 总结:二分图最大匹配问题除了可以用匈牙利算法求解外还可以转化成最大流来做。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=500+10;
const int INF=0x7f7f7f;
struct Edge
{
    int from,to,cap,flow;
};
int m,n,u,v,s,t;
int d[maxn],cur[maxn];
bool vis[maxn];
vector<Edge>edges;
vector<int>G[maxn];
inline void Add_edge(int from,int to,int cap)
{
    edges.push_back((Edge){from,to,cap,0});
    edges.push_back((Edge){to,from,0,0});
    int m=edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}
bool BFS()
{
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    vis[s]=true;
    d[s]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=0;i<G[x].size();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<G[x].size();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)
{
    //this->s=s,this->t=t;
    int flow=0;
    while(BFS())
    {
        memset(cur,0,sizeof(cur));
        flow+=DFS(s,INF);
    }
    return flow;
}
int main()
{
//  freopen("1.sb","r",stdin);
    scanf("%d%d",&m,&n);
    while(~scanf("%d%d",&u,&v)&&u!=-1&&v!=-1)
        Add_edge(u,v,1);
    //s->0 t->n+1
    s=0,t=n+1;
    for(int i=1;i<=m;i++)
        Add_edge(s,i,1);
    for(int i=m+1;i<=n;i++)
        Add_edge(i,t,1);
    //cout<<1<<endl;
    printf("%d",Maxflow(s,t));
    return 0;
}