Evacuation Plan
| Time Limit: 1000MS | Memory Limit: 65536K |
| Special Judge |
Description
The City has a number of municipal buildings and a number of fallout shelters that were build specially to hide municipal workers in case of a nuclear war. Each fallout shelter has a limited capacity in terms of a number of people it can accommodate, and there's almost no excess capacity in The City's fallout shelters. Ideally, all workers from a given municipal building shall run to the nearest fallout shelter. However, this will lead to overcrowding of some fallout shelters, while others will be half-empty at the same time.
To address this problem, The City Council has developed a special evacuation plan. Instead of assigning every worker to a fallout shelter individually (which will be a huge amount of information to keep), they allocated fallout shelters to municipal buildings, listing the number of workers from every building that shall use a given fallout shelter, and left the task of individual assignments to the buildings' management. The plan takes into account a number of workers in every building - all of them are assigned to fallout shelters, and a limited capacity of each fallout shelter - every fallout shelter is assigned to no more workers then it can accommodate, though some fallout shelters may be not used completely.
The City Council claims that their evacuation plan is optimal, in the sense that it minimizes the total time to reach fallout shelters for all workers in The City, which is the sum for all workers of the time to go from the worker's municipal building to the fallout shelter assigned to this worker.
The City Mayor, well known for his constant confrontation with The City Council, does not buy their claim and hires you as an independent consultant to verify the evacuation plan. Your task is to either ensure that the evacuation plan is indeed optimal, or to prove otherwise by presenting another evacuation plan with the smaller total time to reach fallout shelters, thus clearly exposing The City Council's incompetence.
During initial requirements gathering phase of your project, you have found that The City is represented by a rectangular grid. The location of municipal buildings and fallout shelters is specified by two integer numbers and the time to go between municipal building at the location (Xi, Yi) and the fallout shelter at the location (Pj, Qj) is D i,j = |Xi - Pj| + |Yi - Qj| + 1 minutes.
Input
The input consists of The City description and the evacuation plan description. The first line of the input file consists of two numbers N and M separated by a space. N (1 ≤ N ≤ 100) is a number of municipal buildings in The City (all municipal buildings are numbered from 1 to N). M (1 ≤ M ≤ 100) is a number of fallout shelters in The City (all fallout shelters are numbered from 1 to M).
The following N lines describe municipal buildings. Each line contains there integer numbers Xi, Yi, and Bi separated by spaces, where Xi, Yi (-1000 ≤ Xi, Yi ≤ 1000) are the coordinates of the building, and Bi (1 ≤ Bi ≤ 1000) is the number of workers in this building.
The description of municipal buildings is followed by M lines that describe fallout shelters. Each line contains three integer numbers Pj, Qj, and Cj separated by spaces, where Pi, Qi (-1000 ≤ Pj, Qj ≤ 1000) are the coordinates of the fallout shelter, and Cj (1 ≤ Cj ≤ 1000) is the capacity of this shelter.
The description of The City Council's evacuation plan follows on the next N lines. Each line represents an evacuation plan for a single building (in the order they are given in The City description). The evacuation plan of ith municipal building consists of M integer numbers E i,j separated by spaces. E i,j (0 ≤ E i,j ≤ 1000) is a number of workers that shall evacuate from the i th municipal building to the j th fallout shelter.
The plan in the input file is guaranteed to be valid. Namely, it calls for an evacuation of the exact number of workers that are actually working in any given municipal building according to The City description and does not exceed the capacity of any given fallout shelter.
Output
If The City Council's plan is optimal, then write to the output the single word OPTIMAL. Otherwise, write the word SUBOPTIMAL on the first line, followed by N lines that describe your plan in the same format as in the input file. Your plan need not be optimal itself, but must be valid and better than The City Council's one.
Sample Input
3 4
-3 3 5
-2 -2 6
2 2 5
-1 1 3
1 1 4
-2 -2 7
0 -1 3
3 1 1 0
0 0 6 0
0 3 0 2
Sample Output
SUBOPTIMAL
3 0 1 1
0 0 6 0
0 4 0 1
————————————————————強迫症の分割線———————————————————— 前言：還是圖樣圖森破。。。我以為是最小費用最大流，哼唧哼唧寫了個增廣路，心想直接求最優解得了。TLE…… 思路：既然給出了一個殘留網絡，要求隻要比原來更優即可。隻需要找到一個負圈，在圈上的反向邊上+1，那麼一定得到更優解。 負圈産生的原因？ 例如有A、B兩條路可以選擇，假如采用了最小費用的增廣路算法（SPFA）那麼一定是找到最短路增廣咯。 設B更小費用。 A ----------/ \______ S T
B 因為有反向邊存在，是以T->A、A->S存在費用為負值的邊。既然A的費用大，那麼S->B->T->A->S這個環上費用的和為負值，也就是說A這條路多花了錢。消除這個負圈意味着把A這條路的流量流到B這條路上。
就根據殘留網絡建圖。然後在SPFA的時候， 進隊次數超過頂點數的時候return。 這個點一定是因為“可以被負圈重複更新”而反複進隊的。是以它和負圈相連。 通過染色法，找到負圈上的點。（未染色？染色->下一個-> ... ->已染色？該點在環上） 然後在負圈上消掉1個機關的流量即可。 P.S. 一開始600+ms，後來發現，将查找負圈的SPFA改成使用棧，隻需要200+ms。究其原因，是因為棧的話，深度優先（優先取出剛剛更新過的元素），這樣更容易進入負環。 代碼如下：
/*
ID: j.sure.1
PROG:
LANG: C++
*/
/****************************************/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <climits>
#include <iostream>
#define LL long long
using namespace std;
const int INF = 0x3f3f3f3f;
/****************************************/
const int MAXN = 105, N = 222, M = 22222;
int tot, S, T, head[N], path[N], dis[N], enq[N];
bool inq[N];
int n, m, mat[MAXN][MAXN], sum[MAXN];
struct Edge {
int u, v, w, c;
int next;
Edge(){}
Edge(int _u, int _v, int _w, int _c, int _next):
u(_u), v(_v), w(_w), c(_c), next(_next){}
}edge[M];
struct Node {
int x, y, f;
Node(){}
Node(int _x, int _y, int _f):
x(_x), y(_y), f(_f){}
}man[MAXN], house[MAXN];
void init()
{
tot = 0;
memset(head, -1, sizeof(head));
memset(sum, 0, sizeof(sum));
}
void add(int u, int v, int w1, int w2, int c)
{
edge[tot] = Edge(u, v, w1, c, head[u]);
head[u] = tot++;
edge[tot] = Edge(v, u, w2, -c, head[v]);
head[v] = tot++;
}
int spfa()
{
int fron = 0, rear = 0;
memset(inq, 0, sizeof(inq));
memset(enq, 0, sizeof(enq));
memset(dis, 0x3f, sizeof(dis));
dis[T] = 0; inq[T] = 1; enq[T]++;
stack <int> q;
q.push(T);
while(!q.empty()) {
int u = q.top(); q.pop();
inq[u] = false;
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].v;
if(edge[i].w > 0 && dis[v] > dis[u] + edge[i].c) {
dis[v] = dis[u] + edge[i].c;
path[v] = i;
if(!inq[v]) {
inq[v] = true;
q.push(v);
enq[v]++;
if(enq[v] > n+m+1) return v;
}
}
}
}
return -1;
}
void solve(int u)
{
memset(inq, 0, sizeof(inq));
while(!inq[u]) {
inq[u] = 1;
u = edge[path[u]].u;
}//找到負圈中的點
int v = u;
do {
edge[path[v]].w--;
edge[path[v]^1].w++;
v = edge[path[v]].u;
}while(v != u);
memset(mat, 0, sizeof(mat));
for(int i = 1; i <= n; i++) {
for(int j = head[i]; ~j; j = edge[j].next) {
int v = edge[j].v - n;
mat[i][v] += edge[j^1].w;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j < m; j++) {
printf("%d ", mat[i][j]);
}
printf("%d\n", mat[i][m]);
}
}
int main()
{
#ifdef J_Sure
// freopen("000.in", "r", stdin);
// freopen(".out", "w", stdout);
#endif
while(~scanf("%d%d", &n, &m)) {
int x, y, f;
S = 0; T = n + m + 1;
init();
for(int i = 1; i <= n; i++) {
scanf("%d%d%d", &x, &y, &f);
man[i] = Node(x, y, f);
}
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &f);
house[i] = Node(x, y, f);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &f);
int cost = abs(man[i].x - house[j].x) + abs(man[i].y - house[j].y) + 1;
add(i, j+n, INF - f, f, cost);
sum[j] += f;
}
}
for(int j = 1; j <= m; j++) {
add(j+n, T, house[j].f - sum[j], sum[j], 0);
}
int u = spfa();
if(u == -1) {
puts("OPTIMAL");
}
else {
puts("SUBOPTIMAL");
solve(u);
}
}
return 0;
}
![POJ 1284 Primitive Roots (歐拉函數&原根定理)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)