这是挑战上的一道题。
一开始看到这道题，我是直接套最小费用流上去写的，然后无限T。。。
后来看到，原来不是要找最优的情况，只需要输出一组答案比当前结果花费小即可。
然后看书，才知道有消负圈算法这种东西。
费用流中最优的网络是不存在负圈的，最最简单的理解就是，
可以看到上面这个图，我们费用流是在最大流的前提下找最小费用，但是上面这个图肯定不是最大流，s到t还有1个流量单位。
何为负圈？我们在汇点t出发，然后跑最短路（有流量的路才可以通过，这里采用spfa），就会发现这个图会不断循环，先是dis[t] = 0, 然后dis[s] = -1, 然后dis[t] = -1,，然后dis[s] = -2,然后dis[t] = -2，此时节点t入队列次数大于2，所以有负圈。
有负圈说明什么呢？其实就是代表这个图有更优的结果，在负圈这条路上面，只要让正边流量-1，反边流量+1，就可以构成一个更优的结果。
可以把这个看成是一个定理。（反正我是只能理解到这个层面了- -）
所以，那就很好办了，只需要把题目所给的图给建立起来，然后从汇点跑一遍最短路。我没有用挑战上的floyd找负环，用了最习惯的spfa。
但是spfa有一个问题，就是他可以判跑着断跑着发现某个点入队列次数大于点数，就知道存在负圈，但是他不能保证这个点一定在这个圈里面。为什么呢？可以很容易想想来证明，你只要有负圈，这个圈上每个点都会把和他相连的点也更新掉，所以你不能保证这个点一定在这个圈里面，但是你可以保证这个点的前驱的前驱的前驱…………一定在这个圈里面。所以我们只需要记录一下每个点的前驱是谁。如果发现有负环的话，我们从发现的那个点不断找前驱，找到一个点出现了两次，那这个点肯定是在负圈里面的。
我知道哪个点在负圈里面了，此时我再不断找前驱，肯定都是在这个圈里面的。那我们还要更新一下流量，使得正边-1，反边+1（这个正反是在跑这个圈时候相对来说的）。所以我们还要记录一下每个点是由哪条边遍历过来的。
最后，输出答案即可。
代码如下：
#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<utility> #include<stack> #include<algorithm> #include<cstring> #include<string> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 300 + 5; const int maxm = 100000 + 5; int n, m; int head[maxn], to[maxm], front[maxm], flow[maxm], cost[maxm], ppp; int dis[maxn], minflow[maxn]; bool flag[maxn]; int father[maxn], nx[maxn]; int G[105][105]; inline int read() { int x=0,t=1,c; while(!isdigit(c=getchar()))if(c=='-')t=-1; while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*t; } struct MIN_COST_MAX_FLOW { int spfa(int s, int e) { int u, v; int cnt[maxn] = {0}; memset(flag, 0, sizeof(flag)); fill(dis, dis + n + m + 10, INF); dis[s] = 0; queue <int> q; q.push(s); cnt[s]++; while(!q.empty()) { u = q.front(); q.pop(); flag[u] = 0; for(int i = head[u]; ~i; i = front[i]) { v = to[i]; if(flow[i] && dis[v] > dis[u] + cost[i]) { dis[v] = dis[u] + cost[i]; father[v] = u; nx[v] = i; if(!flag[v]) { cnt[v]++; flag[v] = 1; q.push(v); if(cnt[v] > n + m + 2) return v; } } } } return -1; } void solve(int s, int e) { int p, root; root = spfa(s, e); if(root == -1) { cout << "OPTIMAL" << '\n'; return; } cout << "SUBOPTIMAL" << '\n'; memset(flag, 0, sizeof(flag)); p = root; while(1) { //找到一个肯定在环里面的点 if(flag[p]) break; flag[p] = 1; p = father[p]; } root = p; memset(flag, 0, sizeof(flag)); p = root; while(1) {//更新流量 if(flag[p]) break; flag[p] = 1; int tmp = nx[p]; flow[tmp] -= 1; flow[tmp ^ 1] += 1; p = father[p]; } for(int i = 0, key = 0; i < n; i++) {//输出结果 for(int j = 0; j < m; j++) { int ans = INF - flow[key]; if(ans < 0) ans = 0; printf("%d%c", ans, j == m - 1 ? '\n' : ' '); key+=2; } } } void add(int u, int v, int f, int c) { to[ppp] = v, front[ppp] = head[u], flow[ppp] = f, cost[ppp] = c, head[u] = ppp++; } }mcmf; int main() { #ifndef ONLINE_JUDGE freopen("poj_in.txt", "r", stdin); #endif int bx[maxn], by[maxn], bb[maxn], ax[maxn], ay[maxn], ac[maxn]; n=read(), m=read(); memset(head, -1, sizeof(head)); for(int i = 0; i < n; i++) { bx[i] = read(), by[i] = read(), bb[i] = read(); } for(int i = 0; i < m; i++) { ax[i] = read(), ay[i] = read(), ac[i] = read(); } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { G[i][j] = abs(bx[i] - ax[j]) + abs(by[i] - ay[j]) + 1; } } int s = n + m, t = s + 1; int sum[maxn] = {0}; for(int i = 0, key = 0; i < n; i++) { for(int j = 0; j < m; j++) { int tmp = read(); mcmf.add(i, n + j, INF - tmp, G[i][j]); mcmf.add(n + j, i, tmp, -G[i][j]); sum[j] += tmp; } } for(int i = 0; i < n; i++) { mcmf.add(s, i, 0, 0); mcmf.add(i, s, bb[i], 0); } for(int i = 0; i < m; i++) { mcmf.add(n + i, t, ac[i] - sum[i], 0); mcmf.add(t, n + i, sum[i], 0); } mcmf.solve(t, s); return 0; }
