- struct Edge {
- Edge() {}
- Edge(int from, int to, int cap, int flow) : from(from),
- to(to),
- cap(cap),
- flow(flow) {}
- int from,
- to,
- cap,
- flow;
- };
- struct Dinic {
- int n,
- m,
- s,
- t; //结点数,边数(包括反向弧),源点与汇点编号
- vector < Edge > edges; //边表 edges[e]和edges[e^1]互为反向弧
- vector < int > G[maxn]; //邻接表,G[i][j]表示结点i的第j条边在e数组中的序号
- bool vis[maxn]; //BFS使用,标记一个节点是否被遍历过
- int d[maxn]; //d[i]表从起点s到i点的距离(层次)
- int cur[maxn]; //cur[i]表当前正访问i节点的第cur[i]条弧
- void init(int n, int s, int t) {
- this - >n = n,
- this - >s = s,
- this - >t = t;
- for (int i = 1; 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, 0, sizeof(vis));
- queue < int > Q; //用来保存节点编号的
- Q.push(s);
- d[s] = 0;
- 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) {
- vis[e.to] = true;
- d[e.to] = d[x] + 1;
- Q.push(e.to);
- }
- }
- }
- return vis[t];
- }
- //a表示从s到x目前为止所有弧的最小残量
- //flow表示从x到t的最小残量
- int DFS(int x, int a) {
- if (x == t || a == 0) return a;
- int flow = 0,
- f; //flow用来记录从x到t的最小残量
- for (int & i = cur[x]; i < G[x].size(); i++) {
- Edge & e = edges[G[x][i]];
- if (d[x] + 1 == d[e.to] && (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 Maxflow() {
- int flow = 0;
- while (BFS()) {
- memset(cur, 0, sizeof(cur));
- flow += DFS(s, INF);
- }
- return flow;
- }
- }
- DC;
View Code
最小费用最大流模板
- struct Edge
- {
- int from,to,cap,flow,cost;
- Edge(){}
- Edge(int f,int t,int c,int fl,int co):from(f),to(t),cap(c),flow(fl),cost(co){}
- };
- struct MCMF
- {
- int n,m,s,t;
- vector<Edge> edges;
- vector<int> G[maxn];
- bool inq[maxn]; //是否在队列
- int d[maxn]; //Bellman_ford单源最短路径
- int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号
- int a[maxn]; //a[i]表示从s到i的最小残量
- //初始化
- void init(int n,int s,int t)
- {
- this->n=n, this->s=s, this->t=t;
- edges.clear();
- for(int i=0;i<n;++i) G[i].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 &flow, int &cost)
- {
- for(int i=0;i<n;++i) d[i]=INF;
- memset(inq,0,sizeof(inq));
- d[s]=0, a[s]=INF, inq[s]=true, p[s]=0;
- queue<int> Q;
- Q.push(s);
- while(!Q.empty())
- {
- int u=Q.front(); Q.pop();
- inq[u]=false;
- for(int i=0;i<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]=true; }
- }
- }
- }
- if(d[t]==INF) return false;
- flow +=a[t];
- cost +=a[t]*d[t];
- int u=t;
- while(u!=s)
- {
- edges[p[u]].flow += a[t];
- edges[p[u]^1].flow -=a[t];
- u = edges[p[u]].from;
- }
- return true;
- }
- //求出最小费用最大流
- int Min_cost()
- {
- int flow=0,cost=0;
- while(BellmanFord(flow,cost));
- return cost;
- }
- }MM;
View Code
网络流的知识可以参考《挑战程序设计竞赛 Ⅱ》 or 以下链接 链接 、 链接 Ⅱ 、 链接 Ⅲ来源: http://www.bubuko.com/infodetail-2452093.html