首页 > 其他 > 详细

【网络流相关】网络流模型总结——加权二分图

时间：2019-12-18 23:36:42      阅读：100      评论：0      收藏：0      [点我收藏+]

目录

@

引入

最近刷网络流24题时发现了一个比较通用的模型，拿出来总结一下。
Luogu P2756
Luogu P4014
Luogu P4015
Luogu P2763
对于这四道题，都可以构造成二分图模型，使用最大流或者费用流。

P2756 飞行员配对方案问题

其实这题没啥好说的……就是个二分图匹配，最后输出方案只需要枚举原二分图中的边看看哪些残量为\(0\)（也就是作为匹配边）即可。

#include<cstdio>
#include<queue>
using namespace std;
int n,m,num,cnt,u,v,head[20005],cur[20005],dis[20005],ans;
bool vis[20005];
struct data
{
    int sta,to,next,val;
}e[5000005];
void add(int u,int v,int val)
{
    e[++cnt].to=v;
    e[cnt].sta=u;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].val=val;
}
bool bfs(int s,int t)
{
    queue<int> que;
    que.push(s);
    for (int i=1;i<=n+2;i++) dis[i]=0,vis[i]=false,cur[i]=head[i];
    vis[s]=true;
    dis[s]=1;
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        for (int i=head[now];i;i=e[i].next)
        {
            v=e[i].to;
            if (!vis[v]&&e[i].val>0)
            {
                dis[v]=dis[now]+1;
                vis[v]=true;
                if (v==t) return true;
                que.push(v);
            }
        }
    }
    return false;
}
int dfs(int now,int t,int flow)
{
    if (!flow||now==t) return flow;
    int used=0;
    for (int i=cur[now];i;i=e[i].next)
    {
        cur[now]=i;
        v=e[i].to;
        if (dis[now]+1!=dis[v]) continue;
        int tmp=dfs(v,t,min(flow-used,e[i].val));
        if (tmp)
        {
            e[i].val-=tmp;
            e[i^1].val+=tmp;
            used+=tmp;
            if (flow-used==0) return flow;
        }
    }
    return used;
}
void Dinic(int s,int t)
{
    while (bfs(s,t)) ans+=dfs(s,t,0x7fffffff);
}
int main()
{
    scanf("%d%d%d%d",&m,&n,&u,&v);
    cnt=1;
    while (u!=-1&&v!=-1)
    {
        add(u,v,1);
        add(v,u,0);
        scanf("%d%d",&u,&v);
    }
    for (int i=1;i<=m;i++) add(n+1,i,1),add(i,n+1,0);
    for (int i=m+1;i<=n;i++) add(i,n+2,1),add(n+2,i,0);
    Dinic(n+1,n+2);
    if (ans)
    {
        printf("%d\n",ans);
        for (int i=2;i<=cnt-2*n;i+=2) if (e[i].val==0) printf("%d %d\n",e[i].sta,e[i].to);
    }
    else printf("No Solution!");
    return 0;
}

P4014 分配问题

根据题目的描述，可以注意到每一个人只能做一个工件，每一个工件只能给一个人做。所以我们可以考虑使用二分图模型。
把人和工件当成两个点集，就可以使用二分图匹配了。
但是值得注意的是，这题引入了一个效益。
所以我们考虑对于每一个边加入一个费用，人和工件之间的边容量为\(1\)，费用为\(cost[i][j]\)。
然后使用EK算法跑费用流即可，最大效益使用最长路，最小效益使用最短路。

#include<cstdio>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
struct data
{
    int to,next,val,pri;
}e1[10005],e2[10005];
int head1[105],head2[105],flow[105],cost[105],pree[105],prep[105],ans,n,cnt=1;
bool vis[105];
void add(int u,int v,int w,int f)
{
    e1[++cnt].to=v;
    e1[cnt].next=head1[u];
    e1[cnt].val=w;
    e1[cnt].pri=f;
    head1[u]=cnt;
}
int SPFA_short(int s,int t)
{
    queue<int> que;
    que.push(s);
    for (int i=1;i<=t;i++) pree[i]=0,prep[i]=-1,cost[i]=inf,vis[i]=false,flow[i]=0;
    vis[s]=true,pree[s]=0,prep[s]=0,cost[s]=0,flow[s]=inf;
    while (!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for (int i=head1[u];i;i=e1[i].next)
        {
            int v=e1[i].to;
            if (cost[v]>cost[u]+e1[i].pri&&e1[i].val>0)
            {
                flow[v]=min(flow[u],e1[i].val);
                prep[v]=u;
                pree[v]=i;
                cost[v]=cost[u]+e1[i].pri;
                if (!vis[v])
                {
                    que.push(v);vis[v]=true;
                }
            }
        }
    }
    if (prep[t]!=-1) return flow[t];
    else return -1;
}
int SPFA_long(int s,int t)
{
    queue<int> que;
    que.push(s);
    for (int i=1;i<=t;i++) pree[i]=0,prep[i]=-1,cost[i]=-inf,vis[i]=false,flow[i]=0;
    vis[s]=true,pree[s]=0,prep[s]=0,cost[s]=0,flow[s]=inf;
    while (!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for (int i=head2[u];i;i=e2[i].next)
        {
            int v=e2[i].to;
            if (cost[v]<cost[u]+e2[i].pri&&e2[i].val>0)
            {
                flow[v]=min(flow[u],e2[i].val);
                prep[v]=u;
                pree[v]=i;
                cost[v]=cost[u]+e2[i].pri;
                if (!vis[v])
                {
                    que.push(v);vis[v]=true;
                }
            }
        }
    }
    if (prep[t]!=-1) return flow[t];
    else return -1;
}
void EK(int s,int t)
{
    int delta=SPFA_short(s,t);
    while (delta!=-1)
    {
        ans+=cost[t]*delta;
        for (int i=t;i;i=prep[i])
        {
            e1[pree[i]].val-=delta;
            e1[pree[i]^1].val+=delta;
        }
        delta=SPFA_short(s,t);
    }
    printf("%d\n",ans);
    ans=0;
    delta=SPFA_long(s,t);
    while (delta!=-1)
    {
        ans+=cost[t]*delta;
        for (int i=t;i;i=prep[i])
        {
            e2[pree[i]].val-=delta;
            e2[pree[i]^1].val+=delta;
        }
        delta=SPFA_long(s,t);
    }
    printf("%d",ans);
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            int tmp;
            scanf("%d",&tmp);
            add(i,j+n,1,tmp);
            add(j+n,i,0,-tmp);
        }
    int s=2*n+1,t=2*n+2;
    for (int i=1;i<=n;i++) add(s,i,1,0),add(i,s,0,0),add(i+n,t,1,0),add(t,i+n,0,0);
    for (int i=1;i<=t;i++) head2[i]=head1[i];
    for (int i=1;i<=cnt;i++) e2[i]=e1[i];
    EK(s,t);
    return 0;
}

P4015 运输问题

对于多个源点和多个汇点的网络流模型，一个通用的套路就是建立一个超级源点和超级汇点。
由于仓库能发送的流量是有限制的，我们考虑对超源和仓库之间的边加入一个容量限制，费用为\(0\)。
这样就能够意味着仓库可以免费从超源获取一定流量，也就是实现了仓库点存储流量的功能。
同理，零售商连向汇点也应该有一个容量限制，费用自然是为\(0\)。
至于仓库和零售商之间的边，流量没有任何限制，但费用应该为\(1\)。

#include<cstdio>
#include<queue>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
struct data
{
    int to,next,val,pri;
}e1[5005],e2[5005];
int cnt=1,head1[505],head2[5005],cost[505],flow[505],pree[505],prep[505],n,m,minans,maxans;
bool vis[505];
void add(int u,int v,int w,int p)
{
    e1[++cnt].to=v;
    e1[cnt].next=head1[u];
    head1[u]=cnt;
    e1[cnt].val=w;
    e1[cnt].pri=p;
}
int SPFA_short(int s,int t)
{
    queue<int> que;
    for (int i=1;i<=t;i++) cost[i]=inf,pree[i]=0,prep[i]=-1,vis[i]=false;
    que.push(s);
    vis[s]=true;cost[s]=0;pree[s]=0;prep[s]=0;flow[s]=inf;
    while (!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for (int i=head1[u];i;i=e1[i].next)
        {
            int v=e1[i].to;
            if (e1[i].val>0&&cost[v]>cost[u]+e1[i].pri)
            {
                cost[v]=cost[u]+e1[i].pri;
                pree[v]=i;
                prep[v]=u;
                flow[v]=min(flow[u],e1[i].val);
                if (!vis[v])
                {
                    que.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    if (prep[t]!=-1) return flow[t];
    else return -1;
}
int SPFA_long(int s,int t)
{
    queue<int> que;
    for (int i=1;i<=t;i++) cost[i]=-inf,pree[i]=0,prep[i]=-1,vis[i]=false;
    que.push(s);
    vis[s]=true;cost[s]=0;pree[s]=0;prep[s]=0;flow[s]=inf;
    while (!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for (int i=head2[u];i;i=e2[i].next)
        {
            int v=e2[i].to;
            if (e2[i].val>0&&cost[v]<cost[u]+e2[i].pri)
            {
                cost[v]=cost[u]+e2[i].pri;
                pree[v]=i;
                prep[v]=u;
                flow[v]=min(flow[u],e2[i].val);
                if (!vis[v])
                {
                    que.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    if (prep[t]!=-1) return flow[t];
    else return -1;
}
void EK(int s,int t)
{
    int delta=SPFA_short(s,t);
    while (delta!=-1)
    {
        minans+=cost[t]*delta;
        for (int i=t;i;i=prep[i])
        {
            e1[pree[i]].val-=delta;
            e1[pree[i]^1].val+=delta;
        }
        delta=SPFA_short(s,t);
    }
    delta=SPFA_long(s,t);
    while (delta!=-1)
    {
        maxans+=cost[t]*delta;
        for (int i=t;i;i=prep[i])
        {
            e2[pree[i]].val-=delta;
            e2[pree[i]^1].val+=delta;
        }
        delta=SPFA_long(s,t);
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    int s=m+n+1,t=m+n+2;
    for (int i=1;i<=m;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        add(s,i,tmp,0);
        add(i,s,0,0);
    }
    for (int i=1;i<=n;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        add(i+m,t,tmp,0);
        add(t,i+m,0,0);
    }
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
        {
            int tmp;
            scanf("%d",&tmp);
            add(i,j+m,inf,tmp);
            add(j+m,i,0,-tmp);
        }
    for (int i=1;i<=t;i++) head2[i]=head1[i];
    for (int i=1;i<=cnt;i++) e2[i]=e1[i];
    EK(s,t);
    printf("%d\n%d",minans,maxans);
    return 0;
}

P2763 试题库问题

其实这就是一个特殊的二分图匹配，允许某些点被选用多次。
那么我们在给源点连边的时候改一下容量限制即可。

#include<cstdio>
#include<queue>
using namespace std;
int n,k,head[50005],cur[50005],dis[50005],cnt=1;
struct data
{
    int to,next,val;
}e[50005];
void add(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[cnt].val=w;
}
bool bfs(int s,int t)
{
    queue<int> que;
    que.push(s);
    for (int i=1;i<=t;i++) dis[i]=0,cur[i]=head[i];
    while (!que.empty())
    {
        int u=que.front();
        que.pop();
        for (int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if (!dis[v]&&e[i].val>0)
            {
                dis[v]=dis[u]+1;
                if (v==t) return true;
                que.push(v);
            }
        }
    }
    return false;
}
int dfs(int u,int t,int flow)
{
    if (u==t||!flow) return flow;
    int used=0;
    for (int i=cur[u];i;i=e[i].next)
    {
        cur[u]=i;
        int v=e[i].to;
        if (dis[v]!=dis[u]+1) continue;
        int tmp=dfs(v,t,min(flow-used,e[i].val));
        if (!tmp) continue;
        e[i].val-=tmp;
        e[i^1].val+=tmp;
        used+=tmp;
        if (flow==used) return flow;
    }
    return used;
}
int Dinic(int s,int t)
{
    int ans=0;
    while (bfs(s,t)) ans+=dfs(s,t,0x3f3f3f3f);
    return ans;
}
int main()
{
    scanf("%d%d",&k,&n);
    int s=k+n+1,t=k+n+2,tot=0;
    for (int i=1;i<=k;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        tot+=tmp;
        add(s,i,tmp);
        add(i,s,0);
    }
    for (int i=1;i<=n;i++)
    {
        int p;
        add(i+k,t,1);
        add(t,i+k,0);
        scanf("%d",&p);
        for (int j=1;j<=p;j++)
        {
            int tmp;
            scanf("%d",&tmp);
            add(tmp,i+k,1);
            add(i+k,tmp,0);
        }
    }
    if (Dinic(s,t)==tot)
    {
        for (int i=1;i<=k;i++)
        {
            printf("%d: ",i);
            for (int j=head[i];j;j=e[j].next)
            {
                if (e[j].to==s) continue;
                if (e[j].val==0) printf("%d ",e[j].to-k);
            }
            printf("\n");
        }
    }
    else printf("No Solution!");
    return 0;
}

【网络流相关】网络流模型总结——加权二分图

原文：https://www.cnblogs.com/notscience/p/12063773.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！