#include <cstdio> #include <cstring> #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 maxe using 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<n) add((i - 1)*n + j + n*n,i*n + j,oo,0); if (j<n) add((i - 1)*n + j + n*n,(i - 1)*n + j + 1,oo,0); } } int ans = mincost_maxflow(); printf("%d\n",ans); } return 0; }
最大费用最大流和最小费用最大流一样可以用SPFA + Edmonds-Karp解决。//显然SPFA可以求最长路的
貌似先用spfa找出一条增光路,再用ek增加流
有时间再研究研究