最小费用最大流的模板
自己的模板：邻接表。#include<iostream>using namespace std; struct{ int v, cap, cost, next, re; // re记录逆边的下标。}edge[eMax];int n, m, ans;int k, edgeHead[nMax];int que[nMax], pre[nMax], dis[nMax];bool vis[nMax]; void addEdge(int u, int v, int ca, int co){ edge[k].v = v; edge[k].cap = ca; edge[k].cost = co; edge[k].next = edgeHead[u]; edge[k].re = k + 1; edgeHead[u] = k ++; edge[k].v = u; edge[k].cap = 0; edge[k].cost = -co; edge[k].next = edgeHead[v]; edge[k].re = k - 1; edgeHead[v] = k ++;} bool spfa(){ // 源点为0，汇点为n。 int i, head = 0, tail = 1; for(i = 0; i <= n; i ++){ dis[i] = inf; vis[i] = false; } dis[0] = 0; que[0] = 0; vis[u] = true; while(tail > head){ // 这里最好用队列，有广搜的意思，堆栈像深搜。 int u = que[head ++]; for(i = edgeHead[u]; i != 0; i = edge[i].next){ int v = edge[i].v; if(edge[i].cap && dis[v] > dis[u] + edge[i].cost){ dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]){ vis[v] = true; que[tail ++] = v; } } } vis[u] = false; } if(dis[n] == inf) return false; return true;} void end(){ int u, p, sum = inf; for(u = n; u != 0; u = edge[edge[p].re].v){ p = pre[u]; sum = min(sum, edge[p].cap); } for(u = n; u != 0; u = edge[edge[p].re].v){ p = pre[u]; edge[p].cap -= sum; edge[edge[p].re].cap += sum; ans += sum * edge[p].cost; // cost记录的为单位流量费用，必须得乘以流量。 }} int main(){ ... ans = 0; while(spfa()) end(); ... return 0;} 自己的模板：邻接矩阵。#include<iostream>using namespace std; int n, ans;int cap[Max][Max], pre[Max];int cost[Max][Max], dis[Max];int que[Max];bool vis[Max]; bool spfa(){ // 源点为0，汇点为n。 int i, head = 0, tail = 1; for(i = 0; i <= n; i ++){ dis[i] = inf; vis[i] = false; } dis[0] = 0; que[0] = 0; vis[u] = true; while(tail != head){ // 循环队列。 int u = que[head]; for(i = 0; i <= n; i ++) if(cap[u][i] && dis[i] > dis[u] + cost[u][i]){ // 存在路径，且权值变小。 dis[i] = dis[u] + cost[u][i]; pre[i] = u; if(!vis[i]){ vis[i] = true; que[tail ++] = i; if(tail == Max) tail = 0; } } vis[u] = false; head ++; if(head == Max) head = 0; } if(dis[n] == inf) return false; return true;} void end(){ int i, sum = inf; for(i = n; i != 0; i = pre[i]) sum = min(sum, cap[pre[i]][i]); for(i = n; i != 0; i = pre[i]){ cap[pre[i]][i] -= sum; cap[i][pre[i]] += sum; ans += cost[pre[i]][i] * sum; // cost[][]记录的为单位流量费用，必须得乘以流量。 }} int main(){ .... ans = 0; while(spfa()) end(); .... return 0;}