【題意】：一個城市有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 }
|