时间戳

首页 > 技术文章 > 网络流题目总结

网络流题目总结

bxd123 2019-10-13 14:39 原文

最大流

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=1e4+10;
const int M=1e5+10;
struct Edge {
    int to, next, w;
} edge[M<<1];
int head[N],cur[N],pos=1,level[N];
void add(int a, int b, int c) {
    edge[++pos] = (Edge){b, head[a], c};head[a] = pos;
    edge[++pos] = (Edge){a, head[b], 0};head[b] = pos;
}
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    queue<int> q;
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int pos = q.front();q.pop();
        for (int i = head[pos]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (!edge[i].w || level[v]) continue;
            level[v] = level[pos] + 1;
            q.push(v);
        }
    }
    return level[t];
}
int dfs(int s, int t, int flow) {
    if(s==t||flow==0)return flow;
    int f,ret = 0;
    for (int &i = cur[s],v; i; i = edge[i].next) {
         v = edge[i].to;
        if (level[v] == level[s] + 1 && (f=dfs(v,t,min(flow,edge[i].w)))>0) {
            edge[i].w -= f;
            edge[i ^ 1].w += f;
            flow -= f;
            ret += f;
            if(!flow)break;
        }
    }
    return ret;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) memcpy(cur,head,sizeof cur),ret += dfs(s, t, inf);
    return ret;
}
/*
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
50
*/
dinic模板

 

最小路径覆盖模型

P2172 [国家集训队]部落战争

题意：

 

 注意： 每个空地只能被经过一次

题解：

  • 很明显是二分图的最大路径覆盖问题   （ 一个空地只能被经过一次）
  • 所以s连每个空地入度 容量1    出度连t 容量1 能到的话 入度连出度 为1  答案为空地数-dinic   
  • 其实就是用网络流来做二分图匹配算法而已

 

 

 

最小割

 

两点式模型：主要解决分为两个阵营的选与不选问题 通常是求最大效益 一般用最小割模型

P1361 小M的作物

题意：

有两块耕地A和B 有n种作物 第i种作物种到A地可以获得ai效益 种到B可以获得Bi 还有m对组合
第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以获得c2i的额外收益

题解：

  • 显然设置A为S B为T
  • 如果没有组合的话非常简单 连S为ai 连T为bi 即可
  • 考虑到这种组合是将两种作物强行捆绑在一起 可以建立一个虚点 然后两个种子连虚点inf 虚点连A或B连即可

 

 

 

P2057 [SHOI2007]善意的投票

题意： 

 

 

 题解:

  • 睡与不睡就是两点式的两点 s代表睡 t代表不睡
  • 如果一个小朋友想睡  那么连s 容量为1  表示如果不睡（也就是将这条边割掉） 造成的冲突为1
  • 如果两个人是好朋友 那么互相 连一条1（表示造成冲突的代价）  为两点式的固定连法！！！

 

 

 

 

 

 最大权闭合子图： s连项目容量为获利 每个 项目连需求inf  每个需求连t 花费  答案为获利和-最小割

 

P4177 [CEOI2008]order

题意：

有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数，求最大利润。

题解：

  • 看题意很容易想到最大权闭合子图 但是这题多了一种租赁器材的方式
  • 考虑最大权闭合子图的含义  可以看作与s联通表示选择该实验（所以割去器材花费）  与t联通表示放弃该实验（割去实验利益） 
  • 注意到实验连器材的边为inf  表示不可割去   这题租赁的含义恰巧就是该边的容量变为租赁费用
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=2400+10;
const int M=3e6+10;
struct Edge {
    int to, next, w;
} edge[M<<1];
int head[N],cur[N],pos=1,level[N];
void add(int a, int b, int c) {
    edge[++pos] = (Edge){b, head[a], c};head[a] = pos;
    edge[++pos] = (Edge){a, head[b], 0};head[b] = pos;
}
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    queue<int> q;
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int pos = q.front();q.pop();
        for (int i = head[pos]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (!edge[i].w || level[v]) continue;
            level[v] = level[pos] + 1;
            q.push(v);
        }
    }
    return level[t];
}
int dfs(int s, int t, int flow) {
    if(s==t||flow==0)return flow;
    int f,ret = 0;
    for (int &i = cur[s],v; i; i = edge[i].next) {
         v = edge[i].to;
        if (level[v] == level[s] + 1 && (f=dfs(v,t,min(flow,edge[i].w)))>0) {
            edge[i].w -= f;
            edge[i ^ 1].w += f;
            flow -= f;
            ret += f;
            if(!flow)break;
        }
    }
    return ret;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) memcpy(cur,head,sizeof cur),ret += dfs(s, t, inf);
    return ret;
}
int s,t,n,m,sum,x,y,z,q;
int main()
{   
    cin>>n>>m;
    s=n+m+1;t=s+1;
    for(int i=1;i<=n;i++)
    {   
        scanf("%d%d",&x,&q);sum+=x;
        add(s,i,x);
        while(q--)
        {
            scanf("%d%d",&x,&y);
            add(i,x+n,y);
        }
    }
    for(int i=1;i<=m;i++)
    scanf("%d",&x),add(i+n,t,x);
    cout<<sum-dinic(s,t);
    return 0;
}
View Code

 

 

 

CF311E Biologist

题意：

 

题解： 

  • 很明显是一个最大权闭合子图题目
  • 但是一般的最大权闭合子图都是选与不选  这题是二选一  所以很容易想到两点式模型
  • 所以只要将两点式模板按照最大权闭合子图模板魔改一下即可
  • 不满足该“项目”还要倒扣g元 只要将项目利益那条边加g即可  而外面统计的总利益显然是不用加的
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=2e4+10;
const int M=3e6+10;
struct Edge {
    int to, next, w;
} edge[M<<1];
int head[N],cur[N],pos=1,level[N];
void add(int a, int b, int c) {
    edge[++pos] = (Edge){b, head[a], c};head[a] = pos;
    edge[++pos] = (Edge){a, head[b], 0};head[b] = pos;
}
bool bfs(int s, int t) {
    memset(level, 0, sizeof level);
    queue<int> q;
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int pos = q.front();q.pop();
        for (int i = head[pos]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (!edge[i].w || level[v]) continue;
            level[v] = level[pos] + 1;
            q.push(v);
        }
    }
    return level[t];
}
int dfs(int s, int t, int flow) {
    if(s==t||flow==0)return flow;
    int f,ret = 0;
    for (int &i = cur[s],v; i; i = edge[i].next) {
         v = edge[i].to;
        if (level[v] == level[s] + 1 && (f=dfs(v,t,min(flow,edge[i].w)))>0) {
            edge[i].w -= f;
            edge[i ^ 1].w += f;
            flow -= f;
            ret += f;
            if(!flow)break;
        }
    }
    return ret;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) memcpy(cur,head,sizeof cur),ret += dfs(s, t, inf);
    return ret;
}
int s,t,n,m,sum,x,y,z,q,g,op,w,v,k,a[N];
int main()
{   
    cin>>n>>m>>g;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    s=n+m+1;t=s+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(!a[i])add(s,i,x);
        else add(i,t,x);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&w,&k);sum+=w;
        if(!op)
        {
            for(int j=1;j<=k;j++)scanf("%d",&x),add(i+n,x,inf);
            scanf("%d",&x);
            if(x==0)add(s,i+n,w);
            else add(s,i+n,g+w);
        }
        else 
        {
            for(int j=1;j<=k;j++)scanf("%d",&x),add(x,i+n,inf);
            scanf("%d",&x);
            if(x==0)add(i+n,t,w);
            else add(i+n,t,g+w);
        }
    }
    cout<<sum-dinic(s,t);
    return 0;
}
View Code

 

 

 

 

 

最小费用最大流

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5000+10,M=5e4+10;
ll maxflow,mincost;
int last[N],pre[N],dis[N],flow[N];
bool vis[N];
struct Edge{int next,to,flow,dis;}edge[M<<1];
int pos=1,head[N];
void init(){pos=1;memset(head,0,sizeof head);mincost=maxflow=0;}
queue <int> q;
void add(int from,int to,int flow,int dis)//flow流量 dis费用
{
    edge[++pos].next=head[from];edge[pos].flow=flow;edge[pos].dis=dis;edge[pos].to=to;head[from]=pos;
    edge[++pos].next=head[to];edge[pos].flow=0;edge[pos].dis=-dis;edge[pos].to=from;head[to]=pos;
}
bool spfa(int s,int t)
{   
    memset(dis,0x3f,sizeof dis);
    memset(flow,0x3f,sizeof flow);
    memset(vis,0,sizeof vis);
    while (!q.empty()) q.pop();
    dis[s]=0; pre[t]=-1; q.push(s); vis[s]=1;
    int tot=0;
    while (!q.empty())
    {
        int now=q.front(); q.pop(); vis[now]=0;
        for (int i=head[now]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if  (edge[i].flow>0 && dis[to]>dis[now]+edge[i].dis)
            {
                dis[to]=edge[i].dis+dis[now];
                flow[to]=min(edge[i].flow,flow[now]);
                last[to]=i;
                pre[to]=now;
                if (!vis[to])
                {
                    q.push(to); vis[to]=1;
                }
            }
        }
    }
    return pre[t]!=-1;
}
void MCMF(int s,int t)
{
    while (spfa(s,t))
    {
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while (now!=s)
        {
            edge[last[now]].flow-=flow[t];//dis . flow
            edge[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
spfa费用流

 

P1251 餐巾计划问题

题意：

一个餐厅每天早上需要ai条干净毛巾 每天晚上会得到ai条脏毛巾 购买一条毛巾需要p元 快洗一条毛巾需要n天 每条f元 慢洗一条毛巾需要m天 每条s元 问满足每天需求的最少花费

题解：

我们要处理的东西是脏毛巾 所以可以将晚上看作是入度 得到ai条毛巾(s-入)，早上看成是出度 连t 表示完成任务，储存的话每天晚上连到后一天晚上即可（因为储存的显然都是脏毛巾 所以都是晚上） 快洗和慢洗 只要该天晚上连到后面的第n天早上即可。这题没什么技巧 按照题意连即可。

#include< bits/stdc++.h >
using namespace std;
typedef long long ll;
const int N=500000+10,M=5e5+10;
const int inf=0x3f3f3f3f;
ll maxflow,mincost;
int last[N],pre[N],dis[N],flow[N];
bool vis[N];
struct Edge{int next,to,flow,dis;}edge[M<<1];
int pos=1,head[N];
void init(){pos=1;memset(head,0,sizeof head);mincost=maxflow=0;}
queue <int> q;
void add(int from,int to,int flow,int dis)//flow流量 dis费用
{
    edge[++pos].next=head[from];edge[pos].flow=flow;edge[pos].dis=dis;edge[pos].to=to;head[from]=pos;
    edge[++pos].next=head[to];edge[pos].flow=0;edge[pos].dis=-dis;edge[pos].to=from;head[to]=pos;
}
bool spfa(int s,int t)
{   
    memset(dis,0x3f,sizeof dis);
    memset(flow,0x3f,sizeof flow);
    memset(vis,0,sizeof vis);
    while (!q.empty()) q.pop();
    dis[s]=0; pre[t]=-1; q.push(s); vis[s]=1;
    int tot=0;
    while (!q.empty())
    {
        int now=q.front(); q.pop(); vis[now]=0;
        for (int i=head[now]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if  (edge[i].flow>0 && dis[to]>dis[now]+edge[i].dis)
            {
                dis[to]=edge[i].dis+dis[now];
                flow[to]=min(edge[i].flow,flow[now]);
                last[to]=i;
                pre[to]=now;
                if (!vis[to])
                {
                    q.push(to); vis[to]=1;
                }
            }
        }
    }
    return pre[t]!=-1;
}
void MCMF(int s,int t)
{
    while (spfa(s,t))
    {
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while (now!=s)
        {
            edge[last[now]].flow-=flow[t];//dis . flow
            edge[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
int n,m,S,T,p,f,s,NN,x,a[N];
int main()
{
    cin>>NN;
    S=2*NN+1;T=S+1;
    for(int i=1;i<=NN;i++)scanf("%d",&a[i]),add(S,i+NN,a[i],0),add(i,T,a[i],0);
    cin>>p>>m>>f>>n>>s;
    for(int i=1;i<=NN;i++)
    {
        add(S,i,inf,p);
        if(i+1<=NN)add(i+NN,i+NN+1,inf,0);
        if(i+m<=NN)add(i+NN,i+m,inf,f);
        if(i+n<=NN)add(i+NN,i+n,inf,s);
    }
    MCMF(S,T);
    cout<< mincost;
    return 0;
}
code

 

 

P2053 [SCOI2007]修车

题意：

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。

说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

题解：

  •  考虑到极端情况 如果一个工人的效率极高 他一个人修全部的车都比其他人修一辆车要快   但是工人只有一个  所以显然只能将每个工人拆成n个点
  • 建图: 将每个工人拆成n个点（编号为1-n）  每个车主连该工人的所有虚点 费用为 编号*修车基础速度

 

 

 

80人环游世界  *

题意：

　　有m个人到n个城市旅游，每个人可以从任意城市开始旅游，但是只能向去编号大的城市，每个城市有当且仅当vi个人经过，给定每个城市到其他城市的费用，问最小总费用。

题解：

  • 很明显是一个最小费用题
  • 但是比较难处理的是每个城市当且仅当有vi个人经过 之前普遍连法是 将城市拆点  入点连出点vi  其含义为 不超过vi  而不是仅当vi
  • 可以将每个城市拆成两个点 一个点为进入城市 另一个点为离开城市
  • 进入城市连t 容量为vi   ， s连离开城市 容量为vi  完美得保证了城市只有vi个人经过 
  • 离开城市连进入城市  费用为城市之间得费用
  • 一开始有m个人： s-ss-m-0  ss-进入城市

 

 

上下界网络流

 

 

 

有源汇上下界最小费用可行流 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100001;
const int inf=0x3f3f3f3f;
ll maxflow,mincost;
int last[N],pre[N],dis[N],flow[N],d[N];
bool vis[N];
struct Edge{
    int next,to,flow,dis;
}edge[N<<1];
int pos=1,head[N];
void init()
{
    pos=1;memset(head,0,sizeof head);mincost=maxflow=0;
}
queue <int> q;
inline void add(int from,int to,int flow,int dis)//flow流量 dis费用
{
    edge[++pos].next=head[from];edge[pos].flow=flow;edge[pos].dis=dis;edge[pos].to=to;head[from]=pos;
    edge[++pos].next=head[to];edge[pos].flow=0;edge[pos].dis=-dis;edge[pos].to=from;head[to]=pos;
}
void ins(int x,int y,int down,int up,int cost)
{
    add(x,y,up-down,cost);
    d[x]-=down;
    d[y]+=down;
}
bool spfa(int s,int t)
{
    memset(dis,0x3f,sizeof dis);
    memset(flow,0x3f,sizeof flow);
    memset(vis,0,sizeof vis);
    while (!q.empty()) q.pop();
    dis[s]=0; pre[t]=-1; q.push(s); vis[s]=1;
    int tot=0;
    while (!q.empty())
    {
        int now=q.front(); q.pop(); vis[now]=0;
        for (int i=head[now]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if  (edge[i].flow>0 && dis[to]>dis[now]+edge[i].dis)
            {
                dis[to]=edge[i].dis+dis[now];
                flow[to]=min(edge[i].flow,flow[now]);
                last[to]=i;
                pre[to]=now;
                if (!vis[to])
                {
                    q.push(to); vis[to]=1;
                }
            }
        }
    }
    return pre[t]!=-1;
}
inline void MCMF(int s,int t)
{
    while (spfa(s,t))
    {
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while (now!=s)
        {
            edge[last[now]].flow-=flow[t];//dis . flow
            edge[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
int n,m,s,t,ss,x,a,b,S,T;
int main()
{
    scanf("%d",&n);
    s=n+1;t=s+1;S=t+1;T=S+1;

    //正常建图  s为源点 t为汇点    sum为所有得下界*费用和


    
    ins(t,s,0,inf,0);
    for(int i=1;i<=t;i++)
    if(d[i]>0)add(S,i,d[i],0);
    else if(d[i]<0)add(i,T,-d[i],0);
    MCMF(S,T);
    cout<<mincost+sum;

    return 0;
}
//答案即为（求出的费用+原图中边的下界*边的费用）！！！！！！！！！！！！！
有源汇最小费用可行流

 

 

80人环游世界  *

题意：

　　有m个人到n个城市旅游，每个人可以从任意城市开始旅游，但是只能向去编号大的城市，每个城市有当且仅当vi个人经过，给定每个城市到其他城市的费用，问最小总费用。

题解: 

  • 上下界费用流都比较无脑 
  • 按题意连接即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100001;
const int inf=0x3f3f3f3f;
ll maxflow,mincost;
int last[N],pre[N],dis[N],flow[N],d[N];
bool vis[N];
struct Edge{
    int next,to,flow,dis;
}edge[N<<1];
int pos=1,head[N];
void init()
{
    pos=1;memset(head,0,sizeof head);mincost=maxflow=0;
}
queue <int> q;
inline void add(int from,int to,int flow,int dis)//flow流量 dis费用
{
    edge[++pos].next=head[from];edge[pos].flow=flow;edge[pos].dis=dis;edge[pos].to=to;head[from]=pos;
    edge[++pos].next=head[to];edge[pos].flow=0;edge[pos].dis=-dis;edge[pos].to=from;head[to]=pos;
}
void ins(int x,int y,int down,int up,int cost)
{
    add(x,y,up-down,cost);
    d[x]-=down;
    d[y]+=down;
}
bool spfa(int s,int t)
{
    memset(dis,0x3f,sizeof dis);
    memset(flow,0x3f,sizeof flow);
    memset(vis,0,sizeof vis);
    while (!q.empty()) q.pop();
    dis[s]=0; pre[t]=-1; q.push(s); vis[s]=1;
    int tot=0;
    while (!q.empty())
    {
        int now=q.front(); q.pop(); vis[now]=0;
        for (int i=head[now]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if  (edge[i].flow>0 && dis[to]>dis[now]+edge[i].dis)
            {
                dis[to]=edge[i].dis+dis[now];
                flow[to]=min(edge[i].flow,flow[now]);
                last[to]=i;
                pre[to]=now;
                if (!vis[to])
                {
                    q.push(to); vis[to]=1;
                }
            }
        }
    }
    return pre[t]!=-1;
}
inline void MCMF(int s,int t)
{
    while (spfa(s,t))
    {
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while (now!=s)
        {
            edge[last[now]].flow-=flow[t];//dis . flow
            edge[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
int n,m,s,t,ss,x,a,b,S,T,sum;
int main()
{
    scanf("%d%d",&n,&m);
    s=2*n+1;t=s+1;S=t+1;T=S+1;

    int ss=T+1;
    ins(s,ss,m,m,0);
    for(int i=1;i<=n;i++)scanf("%d",&x),ins(i,i+n,x,x,0),ins(ss,i,0,inf,0),ins(i+n,t,0,inf,0);
    for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)
        {scanf("%d",&x);if(x!=-1)ins(i+n,j,0,inf,x);}

        
    ins(t,s,0,inf,0);
    for(int i=1;i<=t;i++)
    if(d[i]>0)add(S,i,d[i],0);
    else if(d[i]<0)add(i,T,-d[i],0);
    MCMF(S,T);
    cout<<mincost+sum;
    return 0;
}
code

 

推荐阅读