精华内容
下载资源
问答
  • 网络流入门

    2019-02-27 17:07:35
    网络流入门 1. 最大流问题 残余网络:由残余容量(每条边上的容量与流量之差)构成的叫残余网络。 增广路定理:如果残余网络中不存在增广路,则当前流就是最大流。 最小割最大流定理: 最大流的流量 = 最小割的...

    网络流入门

    1. 最大流问题

    残余网络:由残余容量(每条边上的容量与流量之差)构成的叫残余网络。

    增广路定理:如果残余网络中不存在增广路,则当前流就是最大流。

    最小割最大流定理:

    最大流的流量 = 最小割的容量

    1.1 EK算法(用BFS寻找增广路)O(nm2)O(nm^2)

    思路:

    寻找增广路,记录从s到每个节点的路径上的最小残量a[i],则a[t]就是s到t的最小残量。由于a[]始终是正数,所以用它代替了vis标志数组。

    edges[e]与edges[e^1]互为反向弧

    1.2 Dinic算法(用DFS在层次网络中多次增广)O(n2m)O(n^2m)

    思路:

    用BFS构建层次网络,用DFS进行多次增广,每进行一次增广后,就要重新构建BFS网络,直到s->t不存在路径。

    层次图:在残量网络中,起点到节点u的高度叫做dis[u],我们把dis[u]看做节点u的层次,只保留每个点出发到下一个层次的弧,得到的图就叫做层次图。 这样,每条“起点->层次1->层次2->层次3->…”的路径都是s->t的最短路。

    1.3 ISAP算法(在增广过程中完成层次网络的更新)O(n2m)O(n^2m)

    思路:

    • Dinic算法中,我们需要每次搜索出层次图,而在ISAP中,我们只需要每次dfs的过程中修改距离标号。

    • 具体来说,我们用d[x]表示残余网络上x到汇点t的最短距离,我们每次沿着d[x]=d[v]+1的路增广。如果点x的出边的点没有发现满足这个条件的那么就说明当前的最短距离d[x]已经过时了,我们需要修改距离标号。修改距离标号,就是让x可以至少有一个点可以增广,所以取所有d[v]中最小的那个加一即可。这样增广下去,当d[s],即s到t的距离大于等于n的时候,就说明至少有一个点经过了两次,即不存在增广路了,这个时候算法结束。

    优化

    • 如果一开始把距离标号都设为0,那么dfs最多需要O(n2)来把距离标号初始化,而我们可以最开始逆向bfs一次,O(n+m)初始化所有距离标号。
    • GAP优化:如果距离标号出现了断层,那么显然不存在新的增广路。我们用一个num数组记录每种层次标号有多少个,如果当前修改了最后一个某种层次标号,那么就出现了前后断层,结束算法。
    • 增广过程中,如果一个点的标号没有修改过,那么它已经遍历过的边不需要再遍历一次,所以我们存下每次遍历到哪条边,下一次从这条边cur[x]开始遍历(因为有可能到这里之后流量用完了,但是还没有增广完)。
    • 最短路的修改具有连续性,即我们不需要每次求后继的标号最小值,而是直接给标号加一。
    • 同Dinic中,如果流量用完了直接退出。

    2. 最小费用最大流问题

    思路:

    类似EK算法,每次用Bellman-Ford算法而非BFS寻找增广路。

    只要初始流是该流量下的最小费用可行流,每次增广后的新流都是新流量下的最小费用流。

    展开全文
  • ACM网络流入门

    千次阅读 2016-05-11 23:58:25
    网络流入门 网络流的最经典应用就是最大流....给定一个图...给出每条边能流过的最大流量...求源点到汇点的最大流量.... 求解网络流的基本思想就是每次寻找增广路(就是源点到汇点的一条可行路)..然后ans+=...
    网络流是ACM图论当中比较重要和难懂的一块,万事开头难,我们还是需要从一个简单的问题引入,这就是网络流中最大流问题。
    网络流入门
    网络流的最经典应用就是最大流....给定一个图...给出每条边能流过的最大流量...求源点到汇点的最大流量.... 求解网络流的基本思想就是每次寻找增广路(就是源点到汇点的一条可行路)..然后ans+=增广路能流过的流量..更新剩余网络..然后再做增广路...直到做不出增广路..关于网络流入门最难理解的地方就是剩余网络了....为什么在找到一条增广路后...不仅要将每条边的可行流量减去增广路能流过的流量...还要将每条边的反向弧加上增广路能流过的流量.?..原因是在做增广路时可能会阻塞后面的增广路...或者说做增广路本来是有个顺序才能找完最大流的.....但我们是任意找的...为了修正...就每次将流量加在了反向弧上...让后面的流能够进行自我调整...剩余网络的更新(就在原图上更新就可以了):  
    复制代码
    1         while (NowPoint!=1) 2         { 3             PrePoint=pre[NowPoint]; 4             Network[PrePoint][NowPoint]-=MinFlow; 5             Network[NowPoint][PrePoint]+=MinFlow; 6             NowPoint=PrePoint;
    复制代码
      7         }最近又复习了下最大流问题,每次看这部分的内容都会有新的收获。可以说最大流问题的资料网上一搜一大把,根本没有必要自己写;但是大部分资料上的专业术语太多了,初学很难理解,至少我当年学这部分的时候前几次就没有看懂。所以我准备备份一点个人的理解。
    图-1
      如图-1所示,在这个运输网络中,源点S和汇点T分别是1,7,各边的容量为C(u,v)。图中红色虚线所示就是一个可行流。标准图示法如图-2所示:
      其中p(u,v) / c(u,v)分别表示该边的实际流量与最大容量。

    关于最大流

      熟悉了什么是网络流,最大流也就很好理解了。就是对于任意的u∈V-{s},使得p(s,u)的和达到最大。上面的运输网络中,最大流如图-3所示:MaxFlow=p(1,2)+p(1,3)=2+1=3。

      在介绍最大流问题之前,先介绍几个概念:残余网络,增广路径,反向弧,最大流定理以及求最大流的Ford-Fulkerson方法。

    残余网络 增广路径 反向弧   观察下图-4,这种状态下它的残余网络如图-5所示:
      也许现在你已经知道什么是残余网络了,对于已经找到一条从S 到T的路径的网络中,只要在这条路径上,把C(u,v)的值更新为C(u,v)-P(u,v),并且添加反向弧C(v,u)。对应的增广路径Path为残留网络上从S到T的一条简单路径。图-4中1,2,4,7就是一条增广路径,当然还有1,3,4,7。

      此外在未做任何操作之前,原始的有向图也是一个残余网络,它仅仅是未做任何更新而已。

    最大流定理

      如果残留网络上找不到增广路径,则当前流为最大流;反之,如果当前流不为最大流,则一定有增广路径。

    Ford-Fulkerson方法

      介绍完上面的概念之后,便可以用Ford-Fulkerson方法求最大流了。为什么叫Ford-Fulkerson方法而不是算法,原因在于可以用多种方式实现这一方法,方式并不唯一。下面介绍一种基于广度优先搜索(BFS)来计算增广路径P的算法:Edmonds-Karp算法。 算法流程如下: 设队列Q:存储当前未访问的节点,队首节点出队后,成为已检查的标点; Path数组:存储当前已访问过的节点的增广路径; Flow数组:存储一次BFS遍历之后流的可改进量; Repeat: Path清空; 源点S进入Path和Q,Path[S]<-0,Flow[S]<-+∞; While Q非空 and 汇点T未访问 do Begin 队首顶点u出对; For每一条从u出发的弧(u,v) do If v未访问 and 弧(u,v) 的流量可改进; Then Flow[v]<-min(Flow[u],c[u][v]) and v入队 and Path[v]<-u; End while   If(汇点T已访问) Then 从汇点T沿着Path构造残余网络;

      Until 汇点T未被访问

      求解最大流流最原始的算法是Ford_Fulkerson..也就是上面提到的每次找任意的找增广路...加上增广路流量再更新剩余网络...可以看出找最大流最耗时的地方就是寻找增广路..Edmonds_Karp是对Ford_Fulkerson的一个优化算法...Ford_Fulkerson是任意寻找增广路...而Edmonds_Karp是每次寻找从源点到汇点可行的最短的增广路...其优势是可以在前期就卡断很多不必要的寻找增广路而又到不了汇点的过程...其优化的方法也很简单..就是将Ford_Fulkerson找增广路的过程用BFS实现.. 一个找最大流更好的优化则是Dinic..优化的地方也是找增广路的过程....Dinic做了一个预处理...将所有点按到源点的距离分层...然后在寻找增广路时..只有要拓展点与当前点的距离差为1时才拓展...其原理我还没弄明白..只知道算法的基本思路... Dinic的过程是 : 1、BFS做出层次网络 2、DFS寻找增广路   CODE: 1 void Dinic()
    复制代码
    2 { 3      while (BFS()) 4      { 5          FindARoad=false; 6          DFS(1,1,oo); 7      } 8 }


    查看原文:http://colorfulshark.cn/wordpress/network-flow-1004.html
    展开全文
  • 最近一段时间再搞网络流,今天终于搞完了!!!!QAQ,好累呀。 首先是关于网络流的基础知识,这部分东西有点多,就不在...网络流--最大流 数据结构与算法分析 - 网络流入门(Network Flow) 知道一些基础知识...

    最近一段时间再搞网络流,今天终于搞完了!!!!QAQ,好累呀。

    首先是关于网络流的基础知识,这部分东西有点多,就不在这里说了,给几个有用的资源。

    先推荐一下建图的博客:链式向前星,静态链表和邻接矩阵建图

    之后就是网络流入门的知识,可以看刘汝佳的紫书里面的知识和这几个博客

    网络流--最大流          数据结构与算法分析 - 网络流入门(Network Flow)

    知道一些基础知识之后,就可以去用比较简单的增广路算法去做几道水题。

    hdu1532最大流模板题   hdu3549——最大流模板题,这两个题不给代码了,都很简单。

    我们现在估计应该都知道最大流问题了,我在这里给出基于EK算法实现的最大流算法,其实就是BFS。

    抛代码模板

    先给出基于邻接表的实现(来源刘汝佳紫书

    struct Edge{
        int from,to,cap,flow;
        Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
    };
    
    struct EdmondsKarp{
        int n,m;
        vector<Edge>edges;//边数的两倍
        vector<int>G[maxn];//邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
        int a[maxn];//当起点到i的可改进量
        int p[maxn];//最短路树上p的入弧编号
    
        void init(int n){
            for(int i=0;i<n;i++)G[i].clear();
            edges.clear();
        }
    
        void AddEdge(int from,int to,int cap){
            edges.push_back(Edge(from,to,cap,0));
            edges.push_back(Edge(to,from,0,0));//反向弧
            m=edges.size();
            G[from].push_back(m-2);
            G[to].push_back(m-1);
        }
    
        int Maxflow(int s,int t){
            int flow=0;
            for(;;){
                memset(a,0,sizeof(a));
                queue<int>Q;
                Q.push(s);
                a[s]=INF;
                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(!a[e.to]&&e.cap>e.flow){
                            p[e.to]=G[x][i];
                            a[e.to]=min(a[x],e.cap-e.flow);
                            Q.push(e.to);
                        }
                    }
                    if(a[t])break;
                }
                if(!a[t])break;
                for(int u=t;u!=s;u=edges[p[u]].from){
                    edges[p[u]].flow+=a[t];
                    edges[p[u]^1].flow-=a[t];
                }
                flow+=a[t];
            }
            return flow;
        }
    }EK;

    然后是基于邻接矩阵的实现,比较简单

    #include <iostream>
    #include <queue>
    #include<string.h>
    using namespace std;
    #define arraysize 201
    int maxData = 0x7fffffff;
    int capacity[arraysize][arraysize]; //记录残留网络的容量
    int flow[arraysize];                //标记从源点到当前节点实际还剩多少流量可用
    int pre[arraysize];                 //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
    int n,m;
    queue<int> myqueue;
    int BFS(int src,int des)
    {
        int i,j;
        while(!myqueue.empty())       //队列清空
            myqueue.pop();
        for(i=1;i<m+1;++i)
        {
            pre[i]=-1;
        }
        pre[src]=0;
        flow[src]= maxData;
        myqueue.push(src);
        while(!myqueue.empty())
        {
            int index = myqueue.front();
            myqueue.pop();
            if(index == des)            //找到了增广路径
                break;
            for(i=1;i<m+1;++i)
            {
                if(i!=src && capacity[index][i]>0 && pre[i]==-1)
                {
                     pre[i] = index; //记录前驱
                     flow[i] = min(capacity[index][i],flow[index]);   //关键:迭代的找到增量
                     myqueue.push(i);
                }
            }
        }
        if(pre[des]==-1)      //残留图中不再存在增广路径
            return -1;
        else
            return flow[des];
    }
    int maxFlow(int src,int des)
    {
        int increasement= 0;
        int sumflow = 0;
        while((increasement=BFS(src,des))!=-1)
        {
             int k = des;          //利用前驱寻找路径
             while(k!=src)
             {
                  int last = pre[k];
                  capacity[last][k] -= increasement; //改变正向边的容量
                  capacity[k][last] += increasement; //改变反向边的容量
                  k = last;
             }
             sumflow += increasement;
        }
        return sumflow;
    }
    int main()
    {
        int i,j;
        int start,end,ci;
        while(cin>>n>>m)
        {
            memset(capacity,0,sizeof(capacity));
            memset(flow,0,sizeof(flow));
            for(i=0;i<n;++i)
            {
                cin>>start>>end>>ci;
                if(start == end)               //考虑起点终点相同的情况
                   continue;
                capacity[start][end] +=ci;     //此处注意可能出现多条同一起点终点的情况
            }
            cout<<maxFlow(1,m)<<endl;
        }
        return 0;
    }

    知道最大流之后,就可以学一下最小割最大流定理,其实就是最大流的另一种表现形式,换了一种问的方式,结果一样。

    最小割是指把两个点割开所花费的最低成本,定理就是最小割等于最大流。

    至于证明可以去网上搜一下。

    然后讲一下最大流进阶的算法(Dinic算法和SAP算法以及优化的ISAP算法)

    Dinic算法的讲解可以看这篇文章:Dinic算法(研究总结,网络流)

    SAP算法和ISAP算法的讲解可以看这个:网络流-最大流问题 ISAP 算法解释

    总的最大流常用算法的时间复杂度为:ISAP>SAP>Dinic>EK≈FF

    下面抛代码

    基于邻接表的Dinic

    #include<stdio.h>
    #include<string.h>
    #include<queue>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxn = 1000 + 10;
    const int INF = 0x3f3f3f3f;
    struct Edge
    {
        int from, to, cap, flow;
        Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
    };
    struct Dinic
    {
        int n, m, s, t;//结点数,边数,(包括反向弧),源点编号和汇点编号 
        vector<int> G[maxn];//边表,edges[e]与edges[e^1]互为反向弧 
        vector<Edge> edges;//邻接表,G[i][j]表示结点 i 的第 j 条边在 e 数组的序号 
        bool vis[maxn];//BFS使用 
        int d[maxn]; //从起点到 i 的距离 
    	int cur[maxn];//当前弧下标 
        void init(int n)
        {
            this->n = n;
            for(int i = 0; i <= n; i++)
                G[i].clear();
            edges.clear();
        }
        void AddEdge(int from, int to, int cap)
        {
            edges.push_back(Edge(from, to, cap, 0));
            edges.push_back(Edge(to, from, 0, 0));
            m = edges.size();
            G[from].push_back(m-2);
            G[to].push_back(m-1);
        }
        bool bfs()
        {
            memset(vis, false, sizeof(vis));
            queue<int> Q;
            d[s] = 0;
            Q.push(s);
            vis[s] = true;
            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)//只考虑残量网络中的弧 
                    {
                        d[e.to] = d[x] + 1;
                        Q.push(e.to);
                        vis[e.to] = true;
                    }
                }
            }
            return vis[t];
        }
        int dfs(int x, int a)
        {
            if(x==t || a==0)
                return a;
            int f, flow = 0;
            for(int& i = cur[x]; i < G[x].size(); i++)//当前弧优化 
            {
                Edge& e = edges[G[x][i]];
                if(d[e.to]==d[x]+1 && (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 max_flow(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;
        }
    }D;
    int main(){
    	int n,m;
        while(scanf("%d%d", &n, &m) != EOF){
            D.init(n+1);
            int u, v, w;
            for(int i = 0; i < m; i++){
                scanf("%d%d%d", &u, &v, &w);
                D.AddEdge(u, v, w);
                D.AddEdge(v, u, 0);
            }
            printf("%d\n", D.max_flow(1,n));
        }
        return 0;
    }
    

    基于邻接矩阵的Dinic算法

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=450;
    int n,m,dis[maxn],E[maxn][maxn];
    bool bfs(int s)
    {
    	memset(dis,-1,sizeof(dis));
    	queue<int> q;
    	dis[s]=0;
    	while(!q.empty()){
    		int now=q.front();
    		q.pop();
    		for(int i = 1;i<=n;i++){
    			if(dis[i]<0&&E[now][i]>0){
    				dis[i]=dis[now]+1;
    				q.push(i); 
    			}
    		} 
    	}
    	if(dis[n]>0) return true;
    	else return false;
    }
    int Find(int x,int low)
    {
    	int a=0;
     	if(x==n) return low;
     	for(int i = 1;i<=n;i++){
     		if(E[x][i]>0&&dis[i]==dis[x]+1&&(a=Find(1,min(low,E[x][i])))){
     			E[x][i]-=a;
     			E[i][x]+=a;
     			return a;
    		}
    	}
        return 0;
    }
    int main(int argc, char** argv) {
    	while(cin>>n>>m){
    		memset(E,0,sizeof(E));
    		for(int i = 1;i<=m;i++){
    			int u,v,w;
    			cin>>u>>v>>w;
    			E[u][v]+=w;
    		}
    		int ans=0;
    		while(bfs(1)){
    			int tmp;
    			while(tmp=Find(1,INT_MAX)){
    				ans+=tmp;
    			}
    		}
    		cout<<ans<<endl;
    	}
    	return 0;
    }

    基于邻接表的ISAP算法

    
    #include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 5010;
    const int MAXN_INT = (1 << 29);
    struct Edge{
        int v, w, nxt;
    };
    bool isFind;
    int head[MAXN];
    Edge edge[MAXN];
    int dis[MAXN], gap[MAXN];
    int n, m, ecnt, aug, maxFlow;
    void init(){
        ecnt = maxFlow = 0;
        memset(gap, 0, sizeof(gap));
        memset(dis, 0, sizeof(dis));
        memset(edge, 0, sizeof(edge));
        memset(head, -1, sizeof(head));
        gap[0] = n;
    }
    void addEdge(int u, int v, int w){
        edge[ecnt].v = v;
        edge[ecnt].w = w;
        edge[ecnt].nxt = head[u];
        head[u] = ecnt++;
    }
    void Find(int s){
        int dx, augc, minDis;
        if(s == n){
            isFind = true;
            maxFlow += aug;
            return;
        }
        augc = aug;
        minDis = n - 1;
        for(int i = head[i]; i + 1; i = edge[i].nxt){
            if(edge[i].w > 0){
                if(dis[s] == dis[edge[i].v] + 1){
                    aug = min(aug, edge[i].w);
                    Find(edge[i].v);
                    if(dis[1] >= n) return;
                    if(isFind){
                        dx = i;
                        break;
                    }
                    aug = augc;
                }
                minDis = min(minDis, dis[edge[i].v]);
            }
        }
        if(!isFind){
            gap[dis[s]]--;
            if(gap[dis[s]] == 0) dis[1] = n;
            dis[s] = minDis + 1;
            gap[dis[s]]++;
        }else{
            edge[dx].w -= aug;
            edge[dx ^ 1].w += aug;
        }
    }
    int main(){
        while(scanf("%d%d", &n, &m) != EOF){
            init();
            int u, v, w;
            for(int i = 0; i < m; i++){
                scanf("%d%d%d", &u, &v, &w);
                addEdge(u, v, w);
                addEdge(v, u, 0);
            }
            while(dis[1] < n){
                isFind = 0;
                aug = MAXN_INT;
                Find(1);
            }
            cout << maxFlow << endl;
        }
        return 0;
    }
    

    基于邻接矩阵的ISAP算法

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define MAXN 222
    #define inf 100000000+1000
    int map[MAXN][MAXN];//存图
    int pre[MAXN];//记录当前点的前驱
    int level[MAXN];//记录距离标号
    int gap[MAXN];//gap常数优化
    int NV,NE;
    
    //入口参数vs源点,vt汇点
    int SAP(int vs,int vt)
    {
    	memset(pre,-1,sizeof(pre));
    	memset(level,0,sizeof(level));
    	memset(gap,0,sizeof(gap));
    	gap[0]=vt;
    	int v,u=pre[vs]=vs,maxflow=0,aug=inf;
    	
    	while(level[vs]<vt)
    	{
    		//寻找可行弧
    		for(v=1;v<=vt;v++)
    		{
    		    if(map[u][v]>0&&level[u]==level[v]+1){
    		         break;
    		    }
    		}
    		if(v<=vt)
    		{
    		   pre[v]=u;
    	       u=v;
    		   if(v==vt)
    		   {
    		   	     int neck=0;
    		         aug=inf;
    		         //寻找当前找到的一条路径上的最大流 , (瓶颈边)
    		         for(int i=v;i!=vs;i=pre[i])
    				 {
    		             if(aug>map[pre[i]][i])
    					 {
    					 	aug=map[pre[i]][i];
    						neck=i;
    					 }
    		         }
    		         maxflow+=aug;
    		         //更新残留网络
    		         for(int i=v;i!=vs;i=pre[i]){
    		             map[pre[i]][i]-=aug;
    		             map[i][pre[i]]+=aug;
    		        }
    			    u=vs;		  //从源点开始继续搜
    		//		u=neck; 	  // Dnic 多路增广优化,下次增广时,从瓶颈边(后面)开始
    		    }
    		}
    		else
    		{
    		    //找不到可行弧
    		    int minlevel=vt;
    		    //寻找与当前点相连接的点中最小的距离标号
    		    for(v=1;v<=vt;v++){
    		         if(map[u][v]>0&&minlevel>level[v]){
    		             minlevel=level[v];
    		         }
    		    }
    		    gap[level[u]]--;//(更新gap数组)当前标号的数目减1;
    		    if(gap[level[u]]==0)break;//出现断层
    		    level[u]=minlevel+1;
    		    gap[level[u]]++;
    		    u=pre[u];
    		}
    	}
    	return maxflow;
    }
    
    int main()
    {
    	int n,m,u,v,cap;
    	while(~scanf("%d%d",&m,&n))
    	{
    		memset(map,0,sizeof(map));
    		for(int i=1;i<=m;i++)
    		{
    		    scanf("%d%d%d",&u,&v,&cap);
    		    map[u][v]+=cap;
    		}
    		printf("%d\n",SAP(1,n));
    	}
    	return 0;
    }

    下面进入另一个经典的网络流问题,最小费用最大流问题。

    其实就是边多了一个权值,费用,然后在求所有的最大流里面最小的费用的最大流。

    关于这个算法的知识可以参考这篇文章:网络流(六)最小费用最大流问题

    也可以看紫书里面的内容,废话不多说,上大白书里面的模板

    struct Edge{
        int from,to,cap,flow,cost;
        Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
    };
    
    struct MCMF{
        int n,m;
        vector<Edge>edges;
        vector<int>G[maxn];
        int inq[maxn];//是否在队列中
        int d[maxn];//Bellman-Ford
        int p[maxn];//上一条弧
        int a[maxn];//可改进量
    
        void init(int n){
            this->n=n;
            for(int i=0;i<n;i++)G[i].clear();
            edges.clear();
        }
    
        void AddEdge(int from,int to,int cap,int cost){
            edges.push_back(Edge(from,to,cap,0,cost));
            edges.push_back(Edge(to,from,0,0,-cost));
            m=edges.size();
            G[from].push_back(m-2);
            G[to].push_back(m-1);
        }
    
        bool BellmanFord(int s,int t,int &flow,long long &cost){
            for(int i=0;i<n;i++)d[i]=INF;
            memset(inq,0,sizeof(inq));
            d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;
    
            queue<int>Q;
            Q.push(s);
            while(!Q.empty()){
                int u=Q.front();Q.pop();
                inq[u]=0;
                for(int i=0;i<(int)G[u].size();i++){
                    Edge &e=edges[G[u][i]];
                    if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
                        d[e.to]=d[u]+e.cost;
                        p[e.to]=G[u][i];
                        a[e.to]=min(a[u],e.cap-e.flow);
                        if(!inq[e.to]){Q.push(e.to);inq[e.to]=1;}
                    }
                }
            }
            if(d[t]==INF)return false;
            flow+=a[t];
            cost+=(long long)d[t]*(long long)a[t];
            for(int u=t;u!=s;u=edges[p[u]].from){
                edges[p[u]].flow+=a[t];
                edges[p[u]^1].flow-=a[t];
            }
            return true;
        }
    
        //需要保证初始网络中没有负权圈
        int MincostMaxflow(int s,int t,long long &cost){
            int flow=0;cost=0;
            while(BellmanFord(s,t,flow,cost));
            return flow;
        }
    }MM;

    其实关于最小费用最大流的求法还有两种,SPFA以及zkw最小费用流(适用于二分图)

    基于SPFA的实现

    struct Edge{
        int to,next,cap,flow,cost;
    }edge[MAXM];
    int head[MAXN],tol;
    int pre[MAXN],dis[MAXN];
    bool vis[MAXN];
    int N;//节点总个数,节点编号从0~N-1
    void init(int n){
        N=n;
        tol=0;
        memset(head,-1,sizeof(head));
    }
    void addedge(int u,int v,int cap,int cost){
        edge[tol].to=v;
        edge[tol].cap=cap;
        edge[tol].cost=cost;
        edge[tol].flow=0;
        edge[tol].next=head[u];
        head[u]=tol++;
        edge[tol].to=u;
        edge[tol].cap=0;
        edge[tol].cost=-cost;
        edge[tol].flow=0;
        edge[tol].next=head[v];
        head[v]=tol++;
    }
    bool spfa(int s,int t){
        queue<int>q;
        for(int i=0;i<N;i++){
            dis[i]=INF;
            vis[i]=false;
            pre[i]=-1;
        }
        dis[s]=0;
        vis[s]=true;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=false;
            for(int i=head[u];i!=-1;i=edge[i].next){
                int v=edge[i].to;
                if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
                    dis[v]=dis[u]+edge[i].cost;
                    pre[v]=i;
                    if(!vis[v]){
                        vis[v]=true;
                        q.push(v);
                    }
                }
            }
        }
        if(pre[t]==-1)return false;
        else return true;
    }
    //返回的是最大流,cost存的是最小费用
    int minCostMaxflow(int s,int t,int &cost){
        int flow=0;
        cost=0;
        while(spfa(s,t)){
            int Min=INF;
            for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
                if(Min>edge[i].cap-edge[i].flow)
                    Min=edge[i].cap-edge[i].flow;
            }
            for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
                edge[i].flow+=Min;
                edge[i^1].flow-=Min;
                cost+=edge[i].cost*Min;
            }
            flow+=Min;
        }
        return flow;
    }

    基于zkw费用流的实现

    struct Edge{
        int to,next,cap,flow,cost;
        Edge(int _to=0,int _next=0,int _cap=0,int _flow=0,int _cost=0):
            to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost){}
    }edge[MAXM];
    struct ZKW_MinCostMaxFlow{
        int head[MAXN],tot;
        int cur[MAXN];
        int dis[MAXN];
        bool vis[MAXN];
        int ss,tt,N;//源点、汇点和点的总个数(编号是0~N-1),不需要额外赋值,调用会直接赋值
        int min_cost,max_flow;
        void init(){
            tot=0;
            memset(head,-1,sizeof(head));
        }
        void addedge(int u,int v,int cap,int cost){
            edge[tot]=Edge(v,head[u],cap,0,cost);
            head[u]=tot++;
            edge[tot]=Edge(u,head[v],0,0,-cost);
            head[v]=tot++;
        }
        int aug(int u,int flow){
            if(u==tt)return flow;
            vis[u]=true;
            for(int i=cur[u];i!=-1;i=edge[i].next){
                int v=edge[i].to;
                if(edge[i].cap>edge[i].flow&&!vis[v]&&dis[u]==dis[v]+edge[i].cost){
                    int tmp=aug(v,min(flow,edge[i].cap-edge[i].flow));
                    edge[i].flow+=tmp;
                    edge[i^1].flow-=tmp;
                    cur[u]=i;
                    if(tmp)return tmp;
                }
            }
            return 0;
        }
        bool modify_label(){
            int d=INF;
            for(int u=0;u<N;u++)
                if(vis[u])
                    for(int i=head[u];i!=-1;i=edge[i].next){
                        int v=edge[i].to;
                        if(edge[i].cap>edge[i].flow&&!vis[v])
                            d=min(d,dis[v]+edge[i].cost-dis[u]);
                    }
            if(d==INF)return false;
            for(int i=0;i<N;i++)
                if(vis[i]){
                    vis[i]=false;
                    dis[i]+=d;
                }
            return true;
        }
        /*
        直接调用获取最小费用和最大流
        输入:start-源点,end-汇点,n-点的总个数(编号从0开始)
        返回值:pair<int,int>第一个是最小费用,第二个是最大流
        */
        pair<int,int> mincostmaxflow(int start,int end,int n){
            ss=start,tt=end,N=n;
            min_cost=max_flow=0;
            for(int i=0;i<n;i++)dis[i]=0;
            while(1){
                for(int i=0;i<n;i++)cur[i]=head[i];
                while(1){
                    for(int i=0;i<n;i++)vis[i]=false;
                    int tmp=aug(ss,INF);
                    if(tmp==0)break;
                    max_flow+=tmp;
                    min_cost+=tmp*dis[ss];
                }
                if(!modify_label())break;
            }
            return make_pair(min_cost,max_flow);
        }
    };

    下面的才是真正的重点——建模和模型的变换

    资料:

    最详细(也可能现在不是了)网络流建模基础

    算法竞赛入门经典——训练指南(简称大白书,真的是经典,有的你第一次看看不懂,等真正做题时才能意识到)

    主要内容:

    建模的方法和技巧。以下来自白书

    方法:

    1.多源多汇问题:有多个源点多个汇点,构造一个超级汇点和超级源点,超级汇点和汇点相连,容量为无穷大,同理汇点也一样

    2.结点容量:拆点,把结点拆成两个,一个入点,一个出点,并且建边,容量为结点的容量。

    3.无源无汇的有容量下界的网络的最大流:详见白书,自己也不是很清楚,通过一道题懂得,在kuangbin带你飞专题里面。

    4.费用和流量平方成正比的最小流:拆边法,详见大白书。

    技巧:

    1.二分图带权最大独立集。

    2.公平分配问题。

    3.区间k覆盖问题

    4.最大闭合子图。

    5.最大密度子图

    以上的内容都是来源于白书,我感觉都是一些很概念性的东西,如果没做题的话就不能体会,所以还是要多做题!!!!

    好了,下面就是牛逼的部分,附上kuangbin带你飞网络流专题的习题和详解。


    kuangbin带你飞网络流专题
    POJ3436——建图和最大流路径记录 题解
    POJ3281——巧妙建图!! 题解
    POJ1087——建图+建图+最大匹配(最大流) 题解
    poj2195——最小费用最大流模板题 题解
    POJ2516——分治+最小费用最大流 题解
    POJ1459——最大流模板题(EK,多方法) 题解
    hdu4280——最大流基础题 题解
    hdu4292——建模题(EK会超时) 题解
    hdu4289——最大流最小割+拆点 题解
    UVA10480——最大流最小割(路径输出)板子题 题解
    hdu2732——建图最大流+拆点 题解
    hdu3338——建图+最大流 题解
    hdu3081——最大流(二分图)+并查集(floyd)+二分 题解
    hdu3416——最短路+最大流 题解

     

     

    展开全文
  • 这是本人网络流入门第二题,不知道怎么解释, 给大家推荐几个博客方便大家入门网络流: 网络流入门博客1 网络流入门博客2 看之前大家可以去百度一下网络流入门术语,这对新手入门网络流会有一些帮助) ...

    (我有什么错误或者你有什么意见,欢迎留言或私聊!谢谢!)

     

    (Ps:以前听说过网络流,想着以后再学,这次中南多校赛也碰到有关网络流的题目,想着这两天试着学学这个吧~~

    这是本人网络流入门第二题,不知道怎么解释,

    给大家推荐几个博客方便大家入门网络流:

    网络流入门博客1

    网络流入门博客2

    看之前大家可以去百度一下网络流入门术语,这对新手入门网络流会有一些帮助)

     

    题意:

      用人话解释:

      1. 给你 n 个点,m个边,num1个发电站,num2个用户;

      2. 每条边有一个负载量,求用户收到的最大用电量;

      3. 显而易见,是网络流中最大流的裸题,只是需要一个简单的处理;

      4. 虽然每个发电站都是一个源点,每个用户都是一个汇点;但是你可以设置一个终极源点和终极汇点

      5. 意思是:终极源点0向每个发电站连一条边,权值为发电站的发电量;每个用户向终极汇点连一条边,权值为用户的限值量;当然还要建反向边;

      6. 如此,题目便简化为求:点0到点n+1的最大流问题,Dinic板子水过,不过这板子应该还能优化。

     

    思路:

      1. 解题思路就在上面。

      2. 说实话,关于算法本身我还说不出什么来,毕竟刚刚入门,(可能还没入门)对很多大神的解释还是一知半解,也就只能套板子写裸题了。

      3. 关于网络流出了Dinic算法还有一些算法如:FF算法,EK算法,E'K'算法,预流推进算法,SAP算法;

      4. 目前准备把每种算法的板子都准备好,板子来源就是从各个大佬博客搜刮!

      5. 搜刮板子的同时,试着理解算法到底优化在哪里,强在哪里,为什么要那样处理;

      6. 先从代码理解算法,然后试着搞懂算法的意思,各种专业术语也一定要理解;首先会写板子题,再试着写有一点难的题;

      7. 听说网络流相关一些题目,难就难在如何建图,能建图就好解决了。看来如果不真正的理解网络流,只拘泥于板子题,实则啥都不会!

     

    题目链接:

    点击做题

    AC代码:

    1266ms

    #include<bits/stdc++.h>
    #define test printf("***\n")
    #define mm1(a) memset((a),-1,sizeof((a)))  
    #define mm0(a) memset((a),0,sizeof((a)))  
    #define mmx(a) memset((a),0x3f,sizeof((a)))  
    #define lowbit(x) (x)&(-(x))
    #define iis std::ios::sync_with_stdio(false)
    using namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    const int N = 10005;
    const int M = 4100005;
    const int X = 999983;
    const int INF = 0x3f3f3f3f;
    const LL INFLL = 0x3f3f3f3f3f3f3f3f;
    const double eps = 1e-8;
    const int mod = 1e9 + 7;
    int n,m,tot,num1,num2;
    int d[N];
    //<font color=black size=4>1</font>
    int head[N];
    struct lp{
        int to,w,nex;
        lp(){}
        lp(int a,int b,int c){to=a;w=b;nex=c;}
    }cw[N*10];
    inline void add(int a,int b,int c){
        cw[++tot]=lp(b,c,head[a]);
        head[a]=tot;
    }
    inline bool bfs(){
        mm1(d);
        queue<int>Q;
        Q.push(0);d[0]=0;
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=head[u];i!=-1;i=cw[i].nex){
                int v=cw[i].to;
                if(cw[i].w&&d[v]==-1){
                    d[v]=d[u]+1;
                    Q.push(v);
                }
            }
        }
        return d[n+1]!=-1;
    }
    //dfs这块有很多优化的地方可以加速,但是我还不会
    //有什么弧优化和多路增广等
    inline int  dfs(int x,int f){
        if(x==n+1||f==0) return f;
        int use=0,w;
        for(int i=head[x];i!=-1;i=cw[i].nex){
            int to=cw[i].to;
            if(d[to]==d[x]+1 && cw[i].w){
                w=dfs(to,min(cw[i].w,f-use));
                cw[i].w-=w,cw[i^1].w+=w;
                use+=w;
                if(use==f) return f;
            }
        }
        return use;
    }
    inline void init(){
        tot=-1;
        mm1(head);
    }
    int main(){
    #ifdef DEBUG
        freopen("D:in.in", "r", stdin);
           freopen("D:out.out", "w", stdout);    
    #endif
        while(cin>>n>>num1>>num2>>m){
            init();
            int x,y,z,a,b;char o;
            for(int i=0;i<m;++i){
                cin>>o>>x>>o>>y>>o>>z;
                add(x+1,y+1,z);add(y+1,x+1,0);
            }
            for(int i=0;i<num1;++i){
                cin>>o>>a>>o>>b;
                add(0,a+1,b);add(a+1,0,0);
            }
            for(int i=0;i<num2;++i){
                cin>>o>>a>>o>>b;
                add(a+1,n+1,b);add(n+1,a+1,0);
            }
            int ans=0;
            while(bfs()){
                ans+=dfs(0,1e7);
            }
            printf("%d\n",ans );
        }
    #ifdef DEBUG
           fclose(stdout);
           fclose(stdin);
    #endif
        return 0;
    }
    View Code

     

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #define mme(a,b) memset((a),(b),sizeof((a)))  
    #define test printf("***\n")
    #define fuck(x) cout<<"* "<<x<<"\n"
    #define iis std::ios::sync_with_stdio(false)
    using namespace std;
    typedef long long LL;
    
    const LL INF=1e17;
    const int MAXN = 1e5+7;
    const int MAXE = MAXN*30;
    struct ISAP{
      int vs,vt,tot,head[MAXN],level[MAXN],gap[MAXN];
      struct lp{
        int to,nex;
        LL w;
      }cw[MAXE];
      inline void Insert(int u,int v,int w){
          cw[++tot].to=v,cw[tot].nex=head[u],head[u]=tot,cw[tot].w=w;
          cw[++tot].to=u,cw[tot].nex=head[v],head[v]=tot,cw[tot].w=0;
      }
      inline LL Min(LL x,LL y){return x<y?x:y;}
      LL SAP(int u,LL fl){
        if (u==vt) return fl;
        LL res=fl;
        for (int i=head[u];i;i=cw[i].nex){
          if (cw[i].w&&level[cw[i].to]+1==level[u]){
            LL t=SAP(cw[i].to,Min(res,cw[i].w));
            cw[i].w-=t,cw[i^1].w+=t;
            if (!(res-=t)) return fl;
          }
        }
        if (!(--gap[level[u]])) level[vt]=vt;
        ++gap[++level[u]];
        return fl-res;
      }
      LL maxFlow(){
        LL ans = 0;
        gap[0]=vt;
        while (level[vt]!=vt){ans+=SAP(vs,INF);}
        return ans;
      }
      void init(int _vs,int _vt){
        memset(head,0,sizeof(head));
        memset(gap,0,sizeof(gap));
        memset(level,0,sizeof(level));
        vs=_vs;vt=_vt;
        tot=1;
      }
    }sap;
    const int N = 805;
    int n,m;
    int vs,vt;
    int num[1<<11];
    int main(){
    #ifndef ONLINE_JUDGE
        freopen("E://ADpan//in.in", "r", stdin);
        //freopen("E://ADpan//out.out", "w", stdout);  
    #endif
      while(~scanf("%d%d",&n,&m)){
        int state = 1<<m;
        mme(num,0);
        vs=state+m+1,vt=state+m+2;
        sap.init(vs,vt);
        for(int i=1;i<=n;++i){
          int tmp=0;
          for(int j=1;j<=m;++j){
            int x;scanf("%d",&x);
            if(x)tmp|=(1<<(j-1));
          }
          num[tmp]++;
        }
        for(int i=1;i<=m;++i){
          int x;scanf("%d",&x);
          sap.Insert(vs,i+state,x);
        }
        for(int i=1;i<state;++i){
          if(num[i]==0)continue;
          sap.Insert(i,vt,num[i]);
          for(int j=0;j<m;++j){
            if(i&(1<<j)){
              sap.Insert(state+j+1,i,num[i]);
            }
          }
        }
        LL ans = sap.maxFlow();
        if(ans>=n)printf("YES\n");
        else printf("NO\n");
      }
      return 0;
    }
    View Code

     

    转载于:https://www.cnblogs.com/Cwolf9/p/8872309.html

    展开全文
  • 网络流入门推荐两位大牛的博客(写的賊好): http://www.cnblogs.com/ZJUT-jiangnan/p/3632525.html. http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html. 在推荐一个题. hdu 1532 ...
  • poj1273网络流入门

    2015-10-11 16:27:24
    poj1273网络流入门题链接:http://poj.org/problem?id=1273 - 题意: 这是一个纯正的,最基础的网络流中最大流问题。 给定 m个点,n条边,其中点1是源点,点m是汇点。接下来n行,给你3个数,边的起点,终点,...
  • poj1459多源点网络流入门 题目链接:http://poj.org/problem?id=1459 题目部分 题意: 简单的说下题意(按输入输出来讲,前面的描述一堆的rubbish,还用来误导人),给你n个点,其中有np个是能提供电力的...
  • poj1459多源点网络流入门

    千次阅读 2015-10-17 11:05:18
    poj1459多源点网络流入门 题目链接:http://poj.org/problem?id=1459 题目部分 题意: 简单的说下题意(按输入输出来讲,前面的描述一堆的rubbish,还用来误导人),给你n个点,其中有np个是能提供电力的点,nc个是...
  • 网络流入门总结

    2020-05-22 13:30:58
    Ford-Fulkerson方法基于增广路定理,当残量网络中中没有增广路时网络达到最大流,关于这些定理的理解和证明还得花些时间。我只能简单理解增广路就像将流量推回去一样,推回去的流量只要能流到汇点那就说明流量还可以...
  • 网络流入门习题

    2020-10-30 17:08:39
    文章目录最大流模型二分图问题[1....最大流模型 二分图问题 习题1是普通二分图,也可以用匈牙利算法做,但是匈牙利算法复杂度略高; 习题2是多重匹配二分图,直接上最大流。 普通二分图和多重匹配二分图的区别: ...
  • 网络流入门—用于最大流的Dinic算法 Posted 2011年05月2日 by comzyh “网络流博大精深”—sideman语 一个基本的网络流问题 感谢WHD的大力支持 最早知道网络流的内容便是最大流问题,最大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,996
精华内容 1,198
关键字:

网络流入门