本文主要是介绍poj 2175 最小费用最大流TLE，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
一条街上有n个大楼，坐标为xi，yi，bi个人在里面工作。
然后防空洞的坐标为pj，qj，可以容纳cj个人。
从大楼i中的人到防空洞j去避难所需的时间为 abs（xi - pi） + （yi - qi） + 1。
现在设计了一个避难计划，指定从大楼i到防空洞j避难的人数 eij。
判断如果按照原计划进行，所有人避难所用的时间总和是不是最小的。
若是，输出“OPETIMAL",若否，输出”SUBOPTIMAL"然后输出一组时间总和更小的避难方案。
解析：
在代表大楼的顶点集合U和代表放空洞的顶点集合V之外，添加源点s和汇点t。
s向各个大楼u连一条容量为楼内人数，费用为0的边；
从防空洞v向t连一条容量为防空洞的人数，费用为0的边；
大楼与防空洞连一条容量为inf，费用为它们之间距离的边。
求最小费用最大流。
...
...
...
然后就超时了- -。
超时代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int maxn = 200 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);struct Edge
{int fr, to, cap, flow, cost;Edge() {}Edge(int _fr, int _to, int _cap, int _flow, int _cost){fr = _fr;to = _to;cap = _cap;flow = _flow;cost = _cost;}
};vector<Edge> edges;
vector<int> g[maxn];
bool inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn];
int V;void init(int v)
{V = v;for (int i = 0; i < V; i++)g[i].clear();edges.clear();memset(p, 0, sizeof(p));memset(a, 0, sizeof(a));
}void addEdge(int fr, int to, int cap, int cost)
{edges.push_back(Edge(fr, to, cap, 0, cost));edges.push_back(Edge(to, fr, 0, 0, -cost));int sz = edges.size();g[fr].push_back(sz - 2);g[to].push_back(sz - 1);
}bool bellmanFord(int s, int t, int& flow, int& cost)
{for (int i = 0; i < V; i++){d[i] = inf;}memset(inq, false, sizeof(inq));d[s] = 0;inq[s] = true;p[s] = 0;a[s] = inf;queue<int> q;q.push(s);while (!q.empty()){int u = q.front();q.pop();inq[u] = false;for (int i = 0; i < g[u].size(); i++){Edge& e = edges[g[u][i]];if (e.cap > e.flow && d[e.to] > d[u] + e.cost){d[e.to] = d[u] + e.cost;p[e.to] = g[u][i];a[e.to] = min(a[u], e.cap - e.flow);if (!inq[e.to]){q.push(e.to);inq[e.to] = true;}}}}if (d[t] == inf)return false;flow += a[t];cost += d[t] * a[t];int u = t;while (u != s){edges[p[u]].flow += a[t];edges[p[u]^1].flow -= a[t];u = edges[p[u]].fr;}return true;
}int MCMF(int s, int t)
{int flow = 0, cost = 0;while (bellmanFord(s, t, flow, cost));return cost;
}int n, m;
int X[maxn], Y[maxn], B[maxn];
int P[maxn], Q[maxn], C[maxn];
int e[maxn][maxn];int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d%d", &n, &m)){for (int i = 0; i < n; i++){scanf("%d%d%d", &X[i], &Y[i], &B[i]);}for (int i = 0; i < m; i++){scanf("%d%d%d", &P[i], &Q[i], &C[i]);}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){scanf("%d", &e[i][j]);}}int s = n + m, t = s + 1;init(t + 1);int costNow = 0;int peopleNum = 0;//0 ~ n - 1 -----大楼//n ~ n + m - 1 -----防空洞for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){int tmp = abs(X[i] - P[j]) + abs(Y[i] - Q[j]) + 1;addEdge(i, n + j, inf, tmp);costNow += e[i][j] * tmp;}}for (int i = 0; i < n; i++){addEdge(s, i, B[i], 0);peopleNum += B[i];}for (int i = 0; i < m; i++){addEdge(n + i, t, C[i], 0);}if (MCMF(s, t) < costNow){puts("SUBOPTIMAL");for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){Edge& e = edges[g[i][n + j]];printf("%d%c", e.cap, j + 1 == m ? '\n' : ' ');}}}else{puts("OPTIMAL");}}return 0;
}
然后这个题目求的不是最小花费。。。
只要判断是不是最小就行了。
所以更高效的求法是：某个流f是同流量中的最小费用流，等价于f的残余网络中没有负圈。
因此，在指派问题对应的图中，增广所给避难计划所对应的流，然后再残余网络上检查有没有负圈，用floyd判断。
如果找到负圈，就沿着负圈增广。
这篇关于poj 2175 最小费用最大流TLE的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
