【题意】：一个城市有n座建筑物，每个建筑物里面有一些人，为了在战争爆发时这些人都可以避难，城市里面建了m座避难所。每座避难所只能容纳有限人数。给出每个建筑物和避难所的坐标（题目要求距离为曼哈顿距离+1）。现在给你一种避难方案，问这种方案是否为最优方案，如果不是，请输出一种比当前更优的方案（不一定最优）。 【题解】：好明显的费用流（距离看成费用），如果此题建费用流模型找最小费用流必定超时，而且题目不需要我们找到最优方案。 定理： 一个费用流是最小费用流的充要条件是这个费用流的残量网络没有负费用圈。
由这个定理，我们只需判断当前方案是否有负费用圈，没有即意味着当前方案为最优方案。
如果有的话，此时只需沿着负费用圈把各边流量增加1，增流之后残量网络对应的方案肯定是一个更优方案（很容易证明）。
实际操作时只需加入一个汇点t，按照当前方案流量像平时一样连边，用spfa从以汇点t为源点找负费用圈，找到负费用圈的充要条件是某个点进入队列大于等于n次。
找到负费用圈就跳出，但此时跳出的点不一定在负费用圈上，我们需要找到一个在负费用圈上的点，可以这样做：
memset(visit, false, sizeof(visit));
while(!visit[i]) {
visit[i] = true, i = pre[i];
}
此时出来的i点必定在负费用圈，因为它在一个循环里面。最后根据前驱修改流量即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "queue"
4 #include "cmath"
5 #include "cstring"
6 using namespace std;
7 const int INF = 99999999;
8 #define maxn 210
9 #define maxm 50005
10 #define MAX 105
11 int s, t, n, m;
12 struct node {
13 int x, y;
14 }a[MAX], b[MAX];
15
16 struct Edge {
17 int u, v, cost, cap, flow, next;
18 }et[maxm];
19 int plan[MAX][MAX], flow[MAX]， num[MAX], cap[MAX], maz[MAX][MAX];
20 int tot, eh[maxn], cnt[maxn], dist[maxn], pre[maxn];
21 bool visit[maxn];
22 void init() {
23 tot = 0;
24 memset(eh, -1, sizeof(eh));
25 }
26
27 void add(int u, int v, int cost, int cap, int flow) {
28 Edge E = {u, v, cost, cap, flow, eh[u]};
29 et[tot] = E;
30 eh[u] = tot++;
31 }
32
33 void addedge(int u, int v, int cost, int cap, int flow) {
34 add(u, v, cost, cap, flow), add(v, u, -cost, 0, -flow);
35 }
36
37 int getdist(node &a, node &b) {
38 return abs(a.x - b.x) + abs(a.y - b.y);
39 }
40
41 bool spfa(int s, int n, int n1) {
42 for(int i = 0; i <= n; i++) visit[i] = false, dist[i] = INF, cnt[i] = 0, pre[i] = -1;
43 dist[s] = 0, visit[s] = true, cnt[s]++;
44 queue<int> que;
45 que.push(s);
46 while(!que.empty()) {
47 int u = que.front();
48 que.pop();
49 visit[u] = false;
50 for(int i = eh[u]; i != -1; i = et[i].next) {
51 int v = et[i].v, cap = et[i].cap, flow = et[i].flow, cost = et[i].cost;
52 if(cap - flow && dist[v] > cost + dist[u]) {
53 dist[v] = cost + dist[u];
54 pre[v] = u; //这里记录当前弧的下标亦可 既pre[v] = i,后面只需相应改一下就可以了
55 if(!visit[v]) {
56 visit[v] = true;
57 que.push(v);
58 cnt[v]++;
59 if(cnt[v] >= n) { //有负环
60 memset(visit, false, sizeof(visit));
61 u = v;
62 while(!visit[u]) { //找到负环上任意一个点
63 visit[u] = true;
64 u = pre[u];
65 }
66 int end = u;
67 u = pre[v = u];
68 do { //更改流量
69 if(u < v && v != t) plan[u][v - n1]++;
70 else if(u > v && u != t) plan[v][u - n1]--;
71 u = pre[v = u];
72 }while(v != end);
73 return false;
74 }
75 }
76 }
77 }
78 }
79 return true;
80 }
81
82 void build() {
83 init();
84 for(int j = 1; j <= m; j++)
85 addedge(j + n, t, 0, cap[j], flow[j]);
86 for(int i = 1; i <= n; i++)
87 for(int j = 1; j <= m; j++)
88 addedge(i, j + n, maz[i][j], INF, plan[i][j]);
89 }
90
91 int main() {
92 scanf("%d%d", &n, &m);
93 for(int i = 1; i <= n; i++)
94 scanf("%d%d%d", &a[i].x, &a[i].y, &num[i]);
95 for(int i = 1; i <= m; i++)
96 scanf("%d%d%d", &b[i].x, &b[i].y, &cap[i]);
97 for(int i = 1; i <= n; i++) {
98 for(int j = 1; j <= m; j++) {
99 maz[i][j] = getdist(a[i], b[j]) + 1;
100 }
101 }
102 for(int i = 1; i <= n; i++) {
103 for(int j = 1; j <= m; j++) {
104 cin >> plan[i][j];
105 }
106 }
107 for(int j = 1; j <= m; j++) {
108 flow[j] = 0;
109 for(int i = 1; i <= n; i++) {
110 flow[j] += plan[i][j];
111 }
112 }
113 t = n + m + 1;
114 build();
115 if(spfa(t, t, n)) cout << "OPTIMAL" << endl;
116 else {
117 cout << "SUBOPTIMAL" << endl;
118 for(int i = 1; i <= n; i++) {
119 for(int j = 1; j <= m; j++) {
120 printf("%d ", plan[i][j]);
121 }
122 printf("\n");
123 }
124 }
125 return 0;
126 }
|