本文共 2911 字，大约阅读时间需要 9 分钟。
#include最大费用最大流和最小费用最大流一样可以用SPFA + Edmonds-Karp解决。//显然SPFA可以求最长路的#include #define maxn 61#define maxv (maxn*maxn*2 + 1)#define maxe (maxv*5)#define oo 2147483647#define min(a,b) ((a>(b)?(b):(a)))#define maxq maxeusing namespace std;struct edge_type{ int x,y,flow,cost,next,op;};int n,m;int a[maxn + 1][maxn + 1];int total,totalv,source,sink;int first[maxv + 1];edge_type g[maxe + 1];int dist[maxv + 1],fa[maxv + 1];bool mark[maxv + 1];int q[maxq + 1];bool spfa(){ memset(mark,0,sizeof(mark)); memset(fa,0,sizeof(fa)); // for (int i=0;i<=totalv;i++) dist[i] = -1; dist[source] = 0; int head,tail; head = 1; tail = 2; q[1] = source; while (head!=tail){ int b = q[head]; mark[b] = 0; for (int temp=first[b];temp;temp=g[temp].next){ if (!g[temp].flow) continue; int y = g[temp].y; int tt; if ((tt = dist[b] + g[temp].cost)>dist[y]){ dist[y] = tt; fa[y] = temp; if (!mark[y]){ mark[y] = 1; q[tail ++] = y; if (tail>maxq) tail = 1; } } } head ++; if (head>maxq) head = 1; } return dist[sink]>=0;}int mincost_maxflow(){ int total_flow,total_cost,cur_flow,cur_cost; total_flow = total_cost = 0; while (spfa()){/* for (int i=1;i<=totalv;i++){ printf("%d ",dist[i]); } printf("\n");*/ cur_flow = oo; cur_cost = 0; for (int temp=fa[sink];temp;temp=fa[g[temp].x]){ cur_flow = min(cur_flow,g[temp].flow); cur_cost += g[temp].cost; } for (int temp=fa[sink];temp;temp=fa[g[temp].x]){ g[temp].flow -= cur_flow; g[g[temp].op].flow += cur_flow; }// printf("%d\n",cur_flow); total_flow += cur_flow; total_cost += cur_cost*cur_flow; }// printf("%d\n",total_flow); return total_cost;}void add(int x,int y,int flow,int cost){ g[++total].x = x; g[total].y = y; g[total].flow = flow; g[total].cost = cost; g[total].op = total + 1; g[total].next = first[x]; first[x] = total; g[++total].x = y; g[total].y = x; g[total].flow = 0; g[total].cost = -cost; g[total].op = total - 1; g[total].next = first[y]; first[y] = total;}int main(){ while (scanf("%d%d",&n,&m)==2){ for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); } total = 0; memset(first,0,sizeof(first)); source = n*n*2 + 1; totalv = source; sink = n*n*2; add(source,1,m,0); for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ add((i - 1)*n + j,(i - 1)*n + j + n*n,1,a[i][j]); add((i - 1)*n + j,(i - 1)*n + j + n*n,oo,0); if (i
貌似先用spfa找出一条增光路，再用ek增加流
有时间再研究研究
转载地址：http://pbeti.baihongyu.com/