【題意】：一個(gè)城市有n座建筑物，每個(gè)建筑物里面有一些人，為了在戰(zhàn)爭(zhēng)爆發(fā)時(shí)這些人都可以避難，城市里面建了m座避難所。每座避難所只能容納有限人數(shù)。給出每個(gè)建筑物和避難所的坐標(biāo)（題目要求距離為曼哈頓距離+1）。現(xiàn)在給你一種避難方案，問(wèn)這種方案是否為最優(yōu)方案，如果不是，請(qǐng)輸出一種比當(dāng)前更優(yōu)的方案（不一定最優(yōu)）。 【題解】：好明顯的費(fèi)用流（距離看成費(fèi)用），如果此題建費(fèi)用流模型找最小費(fèi)用流必定超時(shí)，而且題目不需要我們找到最優(yōu)方案。 定理： 一個(gè)費(fèi)用流是最小費(fèi)用流的充要條件是這個(gè)費(fèi)用流的殘量網(wǎng)絡(luò)沒(méi)有負(fù)費(fèi)用圈。
由這個(gè)定理，我們只需判斷當(dāng)前方案是否有負(fù)費(fèi)用圈，沒(méi)有即意味著當(dāng)前方案為最優(yōu)方案。
如果有的話，此時(shí)只需沿著負(fù)費(fèi)用圈把各邊流量增加1，增流之后殘量網(wǎng)絡(luò)對(duì)應(yīng)的方案肯定是一個(gè)更優(yōu)方案（很容易證明）。
實(shí)際操作時(shí)只需加入一個(gè)匯點(diǎn)t，按照當(dāng)前方案流量像平時(shí)一樣連邊，用spfa從以匯點(diǎn)t為源點(diǎn)找負(fù)費(fèi)用圈，找到負(fù)費(fèi)用圈的充要條件是某個(gè)點(diǎn)進(jìn)入隊(duì)列大于等于n次。
找到負(fù)費(fèi)用圈就跳出，但此時(shí)跳出的點(diǎn)不一定在負(fù)費(fèi)用圈上，我們需要找到一個(gè)在負(fù)費(fèi)用圈上的點(diǎn)，可以這樣做：
memset(visit, false, sizeof(visit));
while(!visit[i]) {
visit[i] = true, i = pre[i];
}
此時(shí)出來(lái)的i點(diǎn)必定在負(fù)費(fèi)用圈，因?yàn)樗谝粋€(gè)循環(huán)里面。最后根據(jù)前驅(qū)修改流量即可。
【代碼】：
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; //這里記錄當(dāng)前弧的下標(biāo)亦可 既pre[v] = i,后面只需相應(yīng)改一下就可以了
55 if(!visit[v]) {
56 visit[v] = true;
57 que.push(v);
58 cnt[v]++;
59 if(cnt[v] >= n) { //有負(fù)環(huán)
60 memset(visit, false, sizeof(visit));
61 u = v;
62 while(!visit[u]) { //找到負(fù)環(huán)上任意一個(gè)點(diǎn)
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 }
|