题目大意：给出一个费用流的模型和已经流过的一些边，问是否存在比这个解更优的解。
思路：直接用原图做一次费用流求最优解会T掉。先介绍费用流消圈定理：如果当前费用流的残量网络中存在负圈，那么当前流不是最优的解。
其实很好理解，结合原图和流过流量之后的反边，若出现了负圈，那么就可以沿着这个负圈增广，而且费用更小。
不过为了解决这个题我们并不需要建立完整的网络流，只需要建立残量网络之后SPFA看是否能找到负环即可。
具体建立方法：
如果一个避难地点有值，那么T向这个避难地点连边，费用0
若当前避难地点没有满，那么向T连边，费用0
若一个位置到一个避难地点有原流量，那么为了能让他流回去，避难地点向那个位置连边，费用曼哈顿距离
所有的位置向所有的避难地点连边，费用曼哈顿距离
找圈什么的随便yy一下就好了- -
CODE：
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#define MAX 210 #define MAXE 100010 #define T (MAX - 1) using namespace std; struct Point{ int x,y; int cnt; void Read() { scanf("%d%d%d",&x,&y,&cnt); } }start[MAX],_end[MAX]; inline int Calc(const Point &p1,const Point &p2) { return abs(p1.x - p2.x) + abs(p1.y - p2.y); } int m,n; int map[MAX][MAX]; int now[MAX]; int head[MAX << 1],total; int _next[MAXE],s[MAXE],aim[MAXE],length[MAXE]; void Add(int x,int y,int z) { _next[++total] = head[x]; s[total] = x; aim[total] = y; length[total] = z; head[x] = total; } int t[MAX]; int f[MAX],from[MAX]; bool v[MAX]; void FindCircle(int x) { puts("SUBOPTIMAL"); memset(v,false,sizeof(v)); int now = x; while(!v[now]) { v[now] = true; now = from[now]; } int src = now; do { if(from[now] <= m && now != T) ++map[from[now]][now - m]; if(from[now] != T && now <= m) --map[now][from[now] - m]; now = from[now]; }while(now != src); for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) printf("%d%c",map[i][j]," \n"[j == n]); } bool SPFA() { static queue
q; memset(f,0x3f,sizeof(f)); f[T] = 0; q.push(T); while(!q.empty()) { int x = q.front(); q.pop(); v[x] = false; for(int i = head[x]; i; i = _next[i]) if(f[aim[i]] > f[x] + length[i]) { f[aim[i]] = f[x] + length[i]; from[aim[i]] = x; if(!v[aim[i]]) { v[aim[i]] = true; q.push(aim[i]); if(++t[aim[i]] > (m + n + 1)) { FindCircle(aim[i]); return true; } } } } return false; } int main() { cin >> m >> n; for(int i = 1; i <= m; ++i) start[i].Read(); for(int i = 1; i <= n; ++i) _end[i].Read(); for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) Add(i,j + m,Calc(start[i],_end[j])); for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) { scanf("%d",&map[i][j]); now[j] += map[i][j]; if(map[i][j]) Add(j + m,i,-Calc(start[i],_end[j])); } for(int i = 1; i <= n; ++i) { if(now[i]) Add(T,i + m,0); if(now[i] < _end[i].cnt) Add(i + m,T,0); } if(!SPFA()) puts("OPTIMAL"); return 0; }