题目
最近房地产商 GDOI (Group of Dumbbells Or Idiots) 从 NOI (Nuts Old Idiots) 手中得到了一块开发土地.
据了解, 这块土地是一块矩形的区域, 可以纵横划分为 \(N\times M\) 块小区域. GDOI 要求将这些区域分为商业区和工业区来开发.
根据不同的地形环境, 每块小区域建造商业区和工业区能取得不同的经济价值. 更具体点, 对于第 \(i\) 行第 \(j\) 列的区域, 建造商业区将得到 \(A_{ij}\) 收益, 建造工业区将得到 \(B_{ij}\) 收益.
另外, 不同的区域连在一起可以得到额外的收益, 即如果区域 \((I,j)\)相邻 (相邻是指两个格子有公共边) 有 \(K\) 块 (显然 \(K\) 不超过 \(4\)) 类型不同于 \((I,j)\)的区域, 则这块区域能增加 \(k\times C_{ij}\) 收益.
经过 Tiger.S 教授的勘察, 收益矩阵 \(A,B,C\) 都已经知道了. 你能帮 GDOI 求出一个收益最大的方案么?
分析
网络流是不可能网络流的, 这辈子都不可能网络流的.
我发现有 \(2^{nm}\) 种解, 然而答案范围只有 \(1000nm\), 说明有大量的重复解, 那还写正解?
这道题我用模拟退火, 随机的是一个矩阵代表每个地方是什么区域.
每次随机一个点做一些微小的变化就可以了.
(如果调参调不下去可以试试多退火几次, 跳出局部最优)
比如我是这样写的:
- int ans = 0;
- for(int i = 0; i <42; i++)
- ans = std::max(SA(), ans);
- printf("%d", ans);
代码
- (不保证每时每刻你提交这份都能 AC)
- #include <bits/stdc++.h>
- const int kMaxSize = 105, mod = 1e9 + 7;
- const double delta = 0.994, sup = 1e17, eps = 1e-17;
- bool plan[kMaxSize][kMaxSize];
- int n, m, a[kMaxSize][kMaxSize], b[kMaxSize][kMaxSize], c[kMaxSize][kMaxSize];
- unsigned sed = time(NULL);
- inline unsigned Rand() {
- sed = ((sed * 0x3abcd1ac + 0xabc12ab2) ^ (sed + 0x1230bace)) % mod;
- return sed;
- }
- int GetIncome() {
- int ans = 0;
- for(int i = 0; i <n; i++)
- for(int j = 0; j < m; j++) {
- if(plan[i][j]) ans += a[i][j];
- else ans += b[i][j];
- if(i - 1>= 0 && plan[i - 1][j] != plan[i][j]) ans += c[i][j];
- if(j - 1>= 0 && plan[i][j - 1] != plan[i][j]) ans += c[i][j];
- if(i + 1 <n && plan[i + 1][j] != plan[i][j]) ans += c[i][j];
- if(j + 1 < m && plan[i][j + 1] != plan[i][j]) ans += c[i][j];
- }
- return ans;
- }
- inline int change(int ans, int x, int y) {
- plan[x][y] ^= 1;
- ans += plan[x][y] ? a[x][y] - b[x][y] : b[x][y] - a[x][y];
- if(x - 1>= 0) {
- ans += plan[x - 1][y] != plan[x][y] ?
- c[x][y] + c[x - 1][y] : -(c[x][y] + c[x - 1][y]);
- }
- if(y - 1>= 0) {
- ans += plan[x][y - 1] != plan[x][y] ?
- c[x][y] + c[x][y - 1] : -(c[x][y] + c[x][y - 1]);
- }
- if(x + 1 <n) {
- ans += plan[x + 1][y] != plan[x][y] ?
- c[x][y] + c[x + 1][y] : -(c[x][y] + c[x + 1][y]);
- }
- if(y + 1 < m) {
- ans += plan[x][y + 1] != plan[x][y] ?
- c[x][y] + c[x][y + 1] : -(c[x][y] + c[x][y + 1]);
- }
- return ans;
- }
- int SA() {
- register int ans, old_ans, new_ans, cnt = 0;
- ans = old_ans = GetIncome();
- for(register double T = sup; T> eps; T *= delta) {
- int x = Rand() % n, y = Rand() % m;
- new_ans = change(old_ans, x, y);
- ans = new_ans> ans ? new_ans : ans;
- if(new_ans> old_ans ||
- Rand() <= exp((new_ans - old_ans) * 1.0 / T) * mod)
- old_ans = new_ans;
- else plan[x][y] ^= 1;
- cnt++;
- }
- return ans;
- }
- int main() {
- srand(time(NULL));
- scanf("%d%d", &n, &m);
- for(int i = 0; i <n; i++)
- for(int j = 0; j < m; j++)
- scanf("%d", &a[i][j]);
- for(int i = 0; i < n; i++)
- for(int j = 0; j < m; j++)
- scanf("%d", &b[i][j]);
- for(int i = 0; i < n; i++)
- for(int j = 0; j < m; j++)
- scanf("%d", &c[i][j]);
- for(int i = 0; i < n; i++)
- for(int j = 0; j < m; j++)
- plan[i][j] = a[i][j]> b[i][j];
- int ans = 0;
- for(int i = 0; i < 42; i++)
- ans = std::max(SA(), ans);
- printf("%d", ans);
- return 0;
- }
结语
不过, Luogu 的数据貌似有点水, 这个代码在一些地方貌似过不了?
[Luogu P1935] [国家集训队]圈地计划
来源: http://www.bubuko.com/infodetail-2945257.html