关于最小费用最大流

发布网友发布时间：2022-05-21 20:59

共3个回答

热心网友时间：2023-11-11 16:26

const
maxn=100;
maxq=100000;

var
p,c,f:array[1..maxn,1..maxn] of longint;
dist,path:array[1..maxn] of longint;
q:array[1..maxq] of longint;
check:array[1..maxn] of 0..1;
n,m:longint;
mark:boolean;

procere init;
var
s,t,r,w,i,j:longint;
begin
readln (n);
readln (m);
for i:=1 to m do begin
readln (s,t,r,w);
c[s,t]:=r;p[s,t]:=w;
end;
end;

procere main;
var
i,j,a,r,l,k:longint;
begin
fillchar(f,sizeof(f),0);
mark:=true;
while mark do begin
q[1]:=1;r:=0;l:=1;
mark:=false;
for i:=2 to n do dist[i]:=maxlongint;
fillchar(check,sizeof(check),0);dist[1]:=0;
fillchar(path,sizeof(path),0);
while r<l do begin
inc(r);
for i:=2 to n do if (c[i,q[r]]<>0) or (c[q[r],i]<>0) then begin
if (c[q[r],i]<>0) and (f[q[r],i]<c[q[r],i]) and (dist[q[r]]+p[q[r],i]<dist[i]) then begin
dist[i]:=dist[q[r]]+p[q[r],i];
path[i]:=q[r];
if check[i]=0 then begin inc(l);q[l]:=i;check[i]:=1;end;
end;
if (c[i,q[r]]<>0) and (f[i,q[r]]<>0) and (dist[q[r]]-p[i,q[r]]<dist[i]) then begin
dist[i]:=dist[q[r]]-p[i,q[r]];
path[i]:=-q[r];
if check[i]=0 then begin inc(l);q[l]:=i;check[i]:=1;end;
end;
end;
check[q[r]]:=0;
end;
if path[n]<>0 then begin
mark:=true;
l:=n;a:=maxlongint;
while l<>1 do begin
k:=abs(path[l]);
if path[l]>0 then begin
if c[k,l]-f[k,l]<a then a:=c[k,l]-f[k,l];
end
else begin
if f[l,k]<a then a:=f[l,k];
end;
l:=k;
end;
l:=n;
while l<>1 do begin
k:=abs(path[l]);
if path[l]>0 then inc(f[k,l],a)
else dec(f[l,k],a);
l:=k;
end;
end;
end;
end;

procere print;
var
i,j,s:longint;
begin
s:=0;for i:=1 to n-1 do inc(s,f[i,n]);
writeln (s);
s:=0;
for i:=1 to n do
for j:=1 to n do inc(s,f[i,j]*p[i,j]);
writeln (s);
end;

begin
init;
main;
print;
end.

最小费用最大流。

你的好长啊。···

把程序看懂后自己可以化嘛。
我暂时找不到用边存储的题目。化为边后不小心错了也有可能。

热心网友时间：2023-11-11 16:27

/*
ID: linjd821
LANG: C++
TASK: http://acm.pku.e.cn/JudgeOnline/problem?id=3422 Kaka's Matrix Travels
*/
/*
算法说明：最小费用最大流
输入：链接表图edge[]+head[], 点个数N,源点src, 汇点dest
输出：ans = 最小费用最大流
代码参考：谢政《网络算法与复杂性理论》网上应该也有英文版的论文，我这个是
连续最短路增广算法（successive shortest path）简称SSP，
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <ctype.h>
#include <map>
#include <string>
#include <set>
#include <bitset>
#include <utility>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <fstream>
#include <list>

using namespace std;

const int MAXN = 5000+10;
const int MAXM = 50000;
const int INF = 1000000000;

struct Edge
{
int next;
int st, ed;
int flow;
int cost;
}edge[MAXM];
int head[MAXN];

int N, K, E, src, dest;
int g[55][55];
int d[MAXN], pre[MAXN];

inline void add_edge(int u, int v, int flow, int cost)
{
edge[E].st = u;
edge[E].ed = v;
edge[E].flow = flow;
edge[E].cost = cost;
edge[E].next = head[u];
head[u] = E++;

edge[E].st = v;
edge[E].ed = u;
edge[E].flow = 0;
edge[E].cost = -cost;
edge[E].next = head[v];
head[v] = E++;
}

//for every node i add_edge i-->i' flow = 1; cost = g[i][j]
//for every path i to j add_edge i'-->j flow = INF; cost = 0;
void BuildGraph()
{
int i, j, u;
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
scanf("%d", &g[i][j]);
memset(head, -1, sizeof(head));
E = 0;
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
{
add_edge((i-1)*N+j, (i-1)*N+j+N*N, 1, -g[i][j]);
if(i != N)
{
add_edge((i-1)*N+j+N*N, i*N+j, INF, 0);
add_edge((i-1)*N+j, i*N+j, INF, 0);
}
if(j != N)
{
add_edge((i-1)*N+j+N*N, (i-1)*N+j+1, INF, 0);
add_edge((i-1)*N+j, (i-1)*N+j+1, INF, 0);
}
if(i == N || (i == N-1 && j == N))
{
add_edge((i-1)*N+j, 2*N*N, INF, 0);
}
}
add_edge(0, 1, K, 0);
src = 0;
N = N*N*2;
dest = N;
}

int SPFA()
{
int que[MAXN][2], rear = 1, front = 0, i, aug = INF;
bool used[MAXN];
memset(used, 0, sizeof(used));
for(i = 0; i <= N; i++)
d[i] = INF;
que[0][0] = src;
que[0][1] = INF;
d[src] = 0;

while(rear != front)
{
int cur = que[front][0];
int cp = que[front][1];
//printf("cur = %d, cp = %d, d[%d] = %d\n", cur, cp, cur, d[cur]);
if(cur == dest) aug = cp;
front = (front+1)%MAXN;
used[cur] = false;
for(i = head[cur]; i != -1; i = edge[i].next)
{
if(edge[i].flow && d[edge[i].ed] > d[cur]+edge[i].cost)
{
d[edge[i].ed] = d[cur]+edge[i].cost;
pre[edge[i].ed] = i;
if(!used[edge[i].ed])
{
used[edge[i].ed] = true;
que[rear][0] = edge[i].ed;
que[rear][1] = min(cp, edge[i].flow);
rear = (rear+1)%MAXN;
}
}
}
}
return aug == INF ? 0 : aug;
}

int MinCostFlow()
{
int i, ans = 0, t;
while((t = SPFA()))
{
ans -= d[dest]*t;
int ptr = dest;
while(ptr != src)
{
ptr = pre[ptr];
edge[ptr].flow -= t;
edge[ptr^1].flow += t;
ptr = edge[ptr].st;
}
}
return ans;
}
int main()
{
while(scanf("%d %d", &N, &K) != EOF)
{
BuildGraph();
printf("%d\n", MinCostFlow());
}
return 0;
}

参考资料：http://blog.csdn.net/soberman/archive/2009/03/09/3974869.aspx

热心网友时间：2023-11-11 16:27

ID: linjd821
LANG: C++
TASK: http://acm.pku.e.cn/JudgeOnline/problem?id=3422 Kaka's Matrix Travels
*/
/*
算法说明：最小费用最大流
输入：链接表图edge[]+head[], 点个数N,源点src, 汇点dest
输出：ans = 最小费用最大流
代码参考：谢政《网络算法与复杂性理论》网上应该也有英文版的论文，我这个是
连续最短路增广算法（successive shortest path）简称SSP，
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <ctype.h>
#include <map>
#include <string>
#include <set>
#include <bitset>
#include <utility>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <fstream>
#include <list>

using namespace std;

const int MAXN = 5000+10;
const int MAXM = 50000;
const int INF = 1000000000;

struct Edge
{
int next;
int st, ed;
int flow;
int cost;
}edge[MAXM];
int head[MAXN];

int N, K, E, src, dest;
int g[55][55];
int d[MAXN], pre[MAXN];

inline void add_edge(int u, int v, int flow, int cost)
{
edge[E].st = u;
edge[E].ed = v;
edge[E].flow = flow;
edge[E].cost = cost;
edge[E].next = head[u];
head[u] = E++;

edge[E].st = v;
edge[E].ed = u;
edge[E].flow = 0;
edge[E].cost = -cost;
edge[E].next = head[v];
head[v] = E++;
}

//for every node i add_edge i-->i' flow = 1; cost = g[i][j]
//for every path i to j add_edge i'-->j flow = INF; cost = 0;
void BuildGraph()
{
int i, j, u;
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
scanf("%d", &g[i][j]);
memset(head, -1, sizeof(head));
E = 0;
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
{
add_edge((i-1)*N+j, (i-1)*N+j+N*N, 1, -g[i][j]);
if(i != N)
{
add_edge((i-1)*N+j+N*N, i*N+j, INF, 0);
add_edge((i-1)*N+j, i*N+j, INF, 0);
}
if(j != N)
{
add_edge((i-1)*N+j+N*N, (i-1)*N+j+1, INF, 0);
add_edge((i-1)*N+j, (i-1)*N+j+1, INF, 0);
}
if(i == N || (i == N-1 && j == N))
{
add_edge((i-1)*N+j, 2*N*N, INF, 0);
}
}
add_edge(0, 1, K, 0);
src = 0;
N = N*N*2;
dest = N;
}

int SPFA()
{
int que[MAXN][2], rear = 1, front = 0, i, aug = INF;
bool used[MAXN];
memset(used, 0, sizeof(used));
for(i = 0; i <= N; i++)
d[i] = INF;
que[0][0] = src;
que[0][1] = INF;
d[src] = 0;

while(rear != front)
{
int cur = que[front][0];
int cp = que[front][1];
//printf("cur = %d, cp = %d, d[%d] = %d\n", cur, cp, cur, d[cur]);
if(cur == dest) aug = cp;
front = (front+1)%MAXN;
used[cur] = false;
for(i = head[cur]; i != -1; i = edge[i].next)
{
if(edge[i].flow && d[edge[i].ed] > d[cur]+edge[i].cost)
{
d[edge[i].ed] = d[cur]+edge[i].cost;
pre[edge[i].ed] = i;
if(!used[edge[i].ed])
{
used[edge[i].ed] = true;
que[rear][0] = edge[i].ed;
que[rear][1] = min(cp, edge[i].flow);
rear = (rear+1)%MAXN;
}
}
}
}
return aug == INF ? 0 : aug;
}

int MinCostFlow()
{
int i, ans = 0, t;
while((t = SPFA()))
{
ans -= d[dest]*t;
int ptr = dest;
while(ptr != src)
{
ptr = pre[ptr];
edge[ptr].flow -= t;
edge[ptr^1].flow += t;
ptr = edge[ptr].st;
}
}
return ans;
}
int main()
{
while(scanf("%d %d", &N, &K) != EOF)
{
BuildGraph();
printf("%d\n", MinCostFlow());
}
return 0;
}

参考资料： http://blog.csdn.net/soberman/archive/2009/03/09/3974869.aspx