本文主要是介绍poj 3422 有流量限制的最小费用流 反用求最大 + 拆点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给一个n*n（50 * 50） 的数字迷宫，从左上点开始走，走到右下点。
每次只能往右移一格，或者往下移一格。
每个格子，第一次到达时可以获得格子对应的数字作为奖励，再次到达则没有奖励。
问走k次这个迷宫，最大能获得多少奖励。
解析：
拆点，拿样例来说明：
3 2
1 2 3
0 2 1
1 4 2
3*3的数字迷宫，走两次最大能获得多少奖励。
将每个点拆成两个点，用来表示第一次到达点 只有这次能得到分数，以及再次到达点 已经没有分数了。
我描述不好，摘一段描述：
将每个点拆成两个，这两点之间连两条边，一条容量为1，费用为该节点的值。
另一条边容量为无穷或k，费用为0，这样保证就算经过这点k次时，费用也只被计算一次。
由于每个点只能往右或者往下走，所以将它和右边及下边的点连一条边，容量为无穷，费用为它的值。
源点向第一个点连边，容量为k，费用为0，最后一个点向汇点连边，容量为k，费用为0。
这样就能保证走k次每个点只取一次了。
将价格建成负的，最小费用就是最大的费用了。
代码：
#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define LL long long
#define lson lo,mi,rt<<1
#define rson mi+1,hi,rt<<1|1
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a,b) memset(a,b,sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)using namespace std;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double ee = exp(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;///50RE 100AC
const int maxv = maxn * maxn + 10;
const double pi = acos(-1.0);
const LL iinf = 0x3f3f3f3f3f3f3f3f;int readT()
{char c;int ret = 0,flg = 0;while(c = getchar(), (c < '0' || c > '9') && c != '-');if(c == '-') flg = 1;else ret = c ^ 48;while( c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c ^ 48);return flg ? - ret : ret;
}//firs - 最短距离 second 顶点编号
typedef pair<int, int> P;struct Edge
{int to, cap, cost, rev;Edge() {}Edge(int _to, int _cap, int _cost, int _rev){to = _to;cap = _cap;cost = _cost;rev = _rev;}
};int V;//顶点数
vector<Edge> g[maxv]; //图的邻接表
int h[maxv]; //残量
int dist[maxv]; //最短距离
int preV[maxv], preE[maxv]; //前驱节点 以及对于的边void init()
{for (int i = 0; i <= V; i++){g[i].clear();}
}//向图中增加一条从fr到to容量为cap费用为cost的边
void addEdge(int fr, int to, int cap, int cost)
{g[fr].push_back(Edge(to, cap, cost, g[to].size()));g[to].push_back(Edge(fr, 0, -cost, g[fr].size() - 1));
}//求解从s到t流量为f的最小费用流
//没有流量为f的流，返回-1
int minCostFlow(int s, int t, int f)
{int res = 0;memset(h, 0, sizeof(h));while (f > 0){priority_queue<P, vector<P>, greater<P> > q;memset(dist, inf, sizeof(dist));dist[s] = 0;q.push(P(0, s));while (!q.empty()){P now = q.top();q.pop();int v = now.second;if (dist[v] < now.first)continue;for (int i = 0; i < g[v].size(); i++){Edge& e = g[v][i];if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];preV[e.to] = v;preE[e.to] = i;q.push(P(dist[e.to], e.to));}}}if (dist[t] == inf){return -1;}for (int v = 0; v < V; v++)h[v] += dist[v];int d = f;for (int v = t; v != s; v = preV[v]){d = min(d, g[preV[v]][preE[v]].cap);}f -= d;res += d * h[t];for (int v = t; v != s; v = preV[v]){Edge& e = g[preV[v]][preE[v]];e.cap -= d;g[v][e.rev].cap += d;}}return res;
}int n, k;
int getId(int i, int j)
{return j * n + i + 1;
}int main()
{
#ifdef LOCALFIN;
#endif // LOCALwhile (~scanf("%d%d", &n, &k)){int s = 0;int t = 2 * n * n + 1;V = t + 1;init();for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){int score = readT();int id = getId(i, j);addEdge(id, id + n * n, 1, -score); //第一次到达点 只有这次能得到分数addEdge(id, id + n * n, k, 0); //再次到达点 已经没有分数了if (i + 1 < n){int down = getId(i + 1, j);addEdge(id + n * n, down, k, 0); //拆出的点与下点相连}if (j + 1 < n){int right = getId(i, j + 1);addEdge(id + n * n, right, k, 0);//拆除的点与左点相连}}}addEdge(s, 1, k, 0);addEdge(2 * n * n, t, k, 0);printf("%d\n", -minCostFlow(s, t, k));}return 0;
}
这篇关于poj 3422 有流量限制的最小费用流 反用求最大 + 拆点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
