跪求 最小费用流 标程

来源:百度知道 编辑:UC知道 时间:2024/05/20 17:24:06
邻接表实现的 最小费最大流
/*
guohao889哥们,你的程序是 最大流 的
不是最小费用最大流的
*/

嘿嘿~这个我有
方法:连续最短路

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;

const int N = 1001;
const int INF = 1 << 28;

class Edge {
public:
int u, v, cuv, cvu, flow, cost;
Edge(int cu, int cv, int ccu, int ccv, int cc) : u(cu), v(cv), cuv(ccu), cvu(ccv), flow(0), cost(cc) {}
int other(int p) const { return p == u ? v : u; }
int cap(int p) const { return p == u ? cuv-flow : cvu+flow; }
int ecost(int) const;
void addFlow(int p, int f) { flow += (p == u ? f : -f); }
};
int Edge::ecost(int p) const {
if(flow == 0) return cost;
else if(flow > 0) return p == u ? cost : -cost;
else return p == u ? -cost : cost;
}

class Network {
private:
vector<Edge> eg;
vector<Edge*> net[N];
Edge *prev[N];
int v, s, t;
int flo