关于网络流算法(3)

实现MCMF的基础上进行尝试针对题目修改代码就方便许多，这里的一个难点是如何输出MCMF对应的各条流路径（网络路径）。实现了MCMF之后很长的一段时间我一直在走弯路，最后发现是自己的测试数据并不方便手算而且一开始采用的模板本身有错误，另一方面因为我之前并没有接触过图论算法，对这些现学的算法实现和运行细节不熟悉。在调整心态之后我决定使用自己设计的图作为调试用例并慢节奏地调试理解，稳扎稳打。

这里有一个博客，作者的思路与我一致，其内容对我有很大帮助。

2.1 多服务器（固定）-多消费结点、无输出的版本

这是调试的一个版本，作为算法发展的基础。

#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int maxm=10000+100;    //最大点数
const int INF=0x3f3f3f3f;

struct edge{        //边：起点、终点、容量、流量、单位费用
    int from,to,c,f,cost;
    edge(int a,int b,int m,int n,int p):from(a),to(b),c(m),f(n),cost(p){}
};

int aabs(int a){
    return a>=0?a:-a;
}

struct MCMF{
    int m,s,t;
    vector<edge> e;
    vector<int> g[maxm];
    int dis[maxm],a[maxm],p[maxm];
    bool vis[maxm];

    void init(int n){        //初始化函数
        for(int i=0;i<=n;i++)g[i].clear();
        e.clear();
    }

    void add(int a,int b,int c,int v){    //加边函数
        e.push_back(edge(a,b,c,0,v));
        e.push_back(edge(b,a,0,0,-v));
        m=e.size();
        g[a].push_back(m-2);
        g[b].push_back(m-1);
    }

    bool spfa(int& flow,int& cost){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        queue<int>q;
        q.push(s);
        vis[s]=1;
        dis[s]=0;
        p[s]=0;
        a[s]=INF;
        while(!q.empty()){
            int u=q.front();q.pop();
            vis[u]=0;
            for(int i=0;i<g[u].size();i++){
                edge tmp=e[g[u][i]];
                if(dis[tmp.to]>dis[u]+tmp.cost &&tmp.c>tmp.f){
                    dis[tmp.to]=dis[u]+tmp.cost;
                    p[tmp.to]=g[u][i];
                    a[tmp.to]=min(a[u],tmp.c-tmp.f);
                    if(!vis[tmp.to]){
                        q.push(tmp.to);
                        vis[tmp.to]=1;
                    }
                }
            }
        }
        if(dis[t]==INF)return 0;
        flow+=a[t];
        cost+=dis[t]*a[t];
        int u=t;
        while(u!=s){
            e[p[u]].f+=a[t];
            e[p[u]^1].f-=a[t];
            u=e[p[u]].from;
        }
        return 1;
    }

    void MF(int s,int t,int &flow,int &cost){    //调用的计算最小费用函数
        this->s=s;
        this->t=t;
        //int flow=0,cost=0;
        while(spfa(flow,cost));
        //return cost;
    }

};

int main()
{
    freopen("C:\Users\lenovo\Desktop\工作\华为挑战赛\testCase0\testCase4.txt", "r", stdin);
    
    //数据准备 
    int n, m, s, t, h;
    int from, to, cap, value;
    int flow, cost, need;
    int loc[maxm], k;
    MCMF mcmf;
    
    //输入第一行 
    cin>>n>>m>>h;
    //初始化 
    mcmf.init(n+h+2);
    //输入网络节点并且add 
    for( int i=1; i<=m; i++ )
    {
        cin>>from>>to>>cap>>value;
        mcmf.add(from, to, cap, value);
        mcmf.add(to, from, cap, value);
    }
    //输入消费结点、add零费用边、建立超级汇点 
    for( int i=1; i<=h; i++ )
    {
        cin>>to>>from>>cap;
        mcmf.add(from, to+n, cap, 0);
        mcmf.add(to+n, from, cap, 0); 
        
        mcmf.add(to+n, n+h+1, cap, 0);    //汇点编号为 n+h+1 
        mcmf.add(n+h+1, to+n, cap, 0);
    }
    //建立超级源点（以0结点为服务器）
    k=2;
    memset(loc,-1,sizeof(loc));
    loc[0]=0;    loc[1]=1;
    for(int i=0;i<k;i++)
    {
        mcmf.add(n+h+2, loc[i], cap, 0);    //源点编号为 n+h+2
        mcmf.add(loc[i], n+h+2, cap, 0);
    }
    
    mcmf.MF(n+h+1,n+h+2,flow,cost);
    cout<<"flow= "<<flow<<endl<<"cost= "<<cost<<endl;
    
    fclose(stdin);
}
//多（固定）服务器单消费节点，含有超级结点 

10 14 2

0 1 1 2
0 9 2 3
1 2 3 1
1 4 4 2
4 9 5 3
9 8 6 1
4 2 7 2
2 6 8 3
4 5 9 1
5 6 10 3
8 6 11 1
6 7 12 2
6 3 13 3
7 3 14 2

0 2 100
1 9 100

2.2 引进DSF函数

往后的代码已经不适合放在公开场合，使用2.1中数据，这边只贴出运行结果：

左图为指定点服务器位置结果，右图为直连结果。

完全自己实现这个DFS算法对我的渣渣水平来说还是有点费劲的，特别是我惊奇地发现在几年前初学C语言时十分熟悉的地址传参，曾玩的很熟的dfs遍历过程中保存路径这种低智商活儿我现在　　居！然！不！会！了！　　震惊之余，在netcan大神的指导之后我才基本清晰了这个DFS的实现思路。

这个DFS其实非常简单，之所以一开始走了弯路是因为对MCMF算法理解不到位，这也暴露出我学习算法的习惯是不求甚解的，理解并不足够到位。一开始我把MCMF想得复杂了，要知道MCMF还是一种最大流算法。

简单对比E-K算法和MCMF中的SPFA算法，E-K算法只考虑边权值，即各“管道”的flow和cap，每次更新残量网络时对于在BFS队列中由当前结点vertexTemp向前遍历到的每个结点vertex[i]，只要考虑更新　vertex[i].flow = min( vertex.cap, vertexTemp.flow )　即可，一旦在BFS中到达了汇点，BFS终止，这样每次BFS找到一条在由源点到汇点的通路，再更新减少这条通路的流量即可，这个过程一直重复到网络资cap源耗尽，汇点不可达。很像一个模拟题是不是？如果理解E-K算法的思想，那么这个过程就是是非常自然的。

下面再考虑使用SPFA算法，有了上面的基础，我们发现其实在E-K算法中我们并不清楚算法过程中对网络cap资源的削减顺序，也就是说不管三七二十一只要汇点可达我就只要找到一条源点到汇点的路径然后让虚拟的流量流过就行，最后得到的结果一定是最大流，另外算法还保存了每条边和每个结点的flow。而在之前的学习中我们知道，解决MCMF问题的一个很关键的定理就是MCMF网络是原始网络每次选择费用最小的增广路经进行增广的结果。因此MCMF算法也是非常简单的东西，就是在E-K的算法基础上，在选择增广路径时不再找到一条可达路径就增广（一旦到达汇点就确定找增广路），而是需要“挑挑拣拣”，寻找可达路径中费用最小的那条。这个问题就转化为寻找按边权cost规划的最短路啊。所以在MCMF的SPFA中我们其实是按照边权cost找到当前图源点至汇点的最短路，作为可达通路之一进行最大流增广。Am I clear?

一开始写printPath()的时候我总是在纠结会不会有一多个流路共用同一条边的情况，因此陷入其中无法解决。后来才意识到，其实MCMF限定的只是两个东西：MF和MC，只要这两个条件是对的，那么对于多源点多汇点问题，就不去管具体的流路是怎么分配的了，在这个题目中更是不会管你信道是否共用电缆，那我们姑且就认为是每条通路都是独占的吧（好奢侈，但是现在想想还是我想多了）。这样的话我们就非常清晰了，这个printPath的过程要满足的条件也大约是题目给出的条件加上MF、MC的条件。

因为整个图的最大流量为Flow，所以从源点发出的最大流量也是Folw，从源点发出最大流量，DFS遍历整个图，在流量耗尽前能到达消费结点的路径被保存，此流路的流量为其上最小cap（瓶颈，独占链路）。这样就能保证每个消费结点的需求都被满足，即最大流条件。另外，因为在之前的SPFA中每个结点的流量被保存，在DFS时也同时考虑结点流量满则不可达的条件，这保证了最小费用条件。

初赛已经结束了，我把代码贴上来吧。还是思维比较僵化，显得很蠢很嫩……

    int DFS(int u, Result *r, int minFlow, int totalFlow)
    {//这个函数的暴露我自己对传参很不熟悉！！ 
        if(vis[u])    return 0;
        else if( u==t ){ 
            r->f = minFlow;
            bestPath.push_back(*r);
            return minFlow;        
        }
        vis[u]=true;
        r->path.push_back(u);
        int tf=totalFlow;
        for(int i=0;i<g[u].size();i++)
        {
            edge &E = e[g[u][i]];
            if(E.f>0)                //结点流量满则不可达 
            {
                int v=E.to;
                if(!vis[v])
                {
                    if(totalFlow>0)    //从源点发出的流量消耗尽，说明此次试探的边不在最大流通路中 
                    {
                        int t = DFS(v, r, min(minFlow, min(totalFlow, E.f)), min(totalFlow, E.f));
                        E.f -= t;
                        totalFlow -= t;
                    }
                    else break;
                }
            }
        }
        vis[u]=false;
        r->path.pop_back();
        return tf; 
    }
};

2.3 初次代码提交

这道题做到这里已经没有时间优化了，因为自己的退火代码出了些问题没有时间和环境调试。

在 netcan大神的耐心帮助下（win7调试不方便，netcan大神帮我编译的），我把输出模块弄好了，交了一发直连，结果如下：