本文共 2415 字，大约阅读时间需要 8 分钟。
题意：
给一个网络中某些边增加容量，增加的总和最大为K，使得最大流最大。
费用流:在某条边增加单位流量的费用。
那么就可以2个点之间建2条边，第一条给定边(u,v,x,0)这条边费用为0
同时另一条边(u,v,K,1)费用为1，那么就可以通过限制在增广时相应的费用即可找出最大流
个人觉得这样做的原因是每次增光都是最优的。所以通过限制最终费用不超过K可以得到最优解
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) { return a % b == 0 ? b : gcd(b, a % b);}const int MAXN = 110;const int INF = 0x3f3f3f3f;struct node{ int u,v,next; int flow,cap,cost;}edge[MAXN * MAXN * 4];int cnt,src,tag;int C,F;int K,N;queue q;bool inq[MAXN];int d[MAXN];int head[MAXN],p[MAXN];int tot = 0;void init(){ memset(head,-1,sizeof(head)); tot = 0;}void add_edge(int u,int v,int cap,int cost){ edge[cnt].u = u; edge[cnt].v = v; edge[cnt].cap = cap; edge[cnt].flow = 0; edge[cnt].cost = cost; edge[cnt].next = head[u]; head[u] = cnt++; //反向 edge[cnt].v = u; edge[cnt].u = v; edge[cnt].flow = 0; edge[cnt].cap = 0; edge[cnt].cost = - cost; edge[cnt].next = head[v]; head[v] = cnt++;}bool SPFA(int s, int t){ while (!q.empty()) q.pop(); memset(inq,false,sizeof(inq)); memset(d,0x3f,sizeof(d)); memset(p,-1,sizeof(p)); d[s] = 0; q.push(s); inq[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if (d[v] > d[u] + edge[i].cost && edge[i].cap > edge[i].flow) { d[v] = d[u] + edge[i].cost; p[v] = i; if (!inq[v]) { q.push(v); inq[v] = true; } } } } if(d[tag] == INF) return false; int a = INF; for (int i = p[tag]; i != -1; i = p[edge[i].u]) a = min(a,edge[i].cap - edge[i].flow); if(C + d[tag] * a > K) { F += (K - C) / d[tag]; return false; } return true;}void slove(){ C = F = 0; while(SPFA(src,tag)) { int a = INF; for (int i = p[tag]; i != -1; i = p[edge[i].u]) a = min(a,edge[i].cap - edge[i].flow); for (int i = p[tag]; i != -1; i = p[edge[i].u]) { edge[i].flow += a; edge[i ^ 1].flow -= a; } C += d[tag] * a; F += a; }}int main(){ while (scanf("%d%d",&N,&K) != EOF) { init(); for (int i = 1 ; i <= N ; i++) for (int j = 1 ; j <= N ; j++) { int x; scanf("%d",&x); if (x) { add_edge(i,j,x,0); add_edge(i,j,K,1); } } src = 1; tag = N; slove(); printf("%d\n",F); } return 0;}
转载于:https://www.cnblogs.com/Commence/p/4928476.html