Flow construction

题目:

  给出N个节点M条水管，要求在满足上下界的情况下。满足起点最小的流量。

算法：

   这是最小流？？？？不知道。只知道用求解上下界最大流的方法就过了。

   做这题收获了很多东西。知道了同一点的flow是真实的流量值，虽然以前在书上或论文中看到过，不过印象不深，但是经过这题深刻的懂了。就是这题输出的时候有点麻烦。。。要记录每次的路径，然后用我刚才说的那个，同一个点的flow是真实的流量值!!!!

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 1 << 28;
const int MAXN = 200 + 10;
///////////////////////////////////////

//上下界最小流

struct Edge{
    int from,to,cap,flow,cost;
    Edge(){};
    Edge(int _from,int _to,int _cap,int _flow)
        :from(_from),to(_to),cap(_cap),flow(_flow){};
};
vector<Edge> edges;
vector<int> G[MAXN];
int cur[MAXN],d[MAXN];
bool vst[MAXN];
int N,M,src,sink;


////////////////////////////////

//上下界网络流
int sum;
int in[MAXN],id[MAXN*MAXN],low[MAXN*MAXN];


void init(){
    src = http://www.mamicode.com/N + 2; sink = src + 1;>

 
sgu Flow construction