题解 P1073 【最优贸易】
Ciyang
·
·
题解
此题为什么没有模拟退火题解???我来水一发模拟退火.
废话:这个题我们组内刚考试了,当时模拟退火和SPFA是写对了,但题目读成了最差贸易(最大亏损利润)...然后A了一个点,WA了一堆???下载了数据点不懂问大佬,结果是自己读错题了...
先看题目重要内容:
阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行
任何城市可以重复经过多次，但不要求经过所有 n 个城市
他会选择一个经过的城市买入水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。
他决定这个贸易只进行最多一次，在赚不到差价的情况下他就无需进行贸易
我的分析如下:
阿龙一定会有一个买入城市和卖出城市,并且第 1 号城市一定能到达买入城市,卖出城市一定能到达第 n 号城市,而且买入城市一定能到达卖出城市
因此我们可以用模拟退火设置买入和卖出城市,只要满足这三个条件,那么就更新答案.
既然第 1 号城市和第 n 号城市极为重要,因此在输入完数据后,先用SPFA正向跑第 1 号城市能到达的城市并存到bool数组里,再用SPFA反向跑第 2 号城市能到达的城市并存到bool数组里(注意要是反向)
在输入时,我用了贪心的思想,记录价格最大城市和价格最小城市,先判断一下能不能从这两个城市买,一定是最大的差价,保证了一点正确率.
在每次检测中,都以买入城市为起点跑一遍SPFA,检测是否到达卖出城市.(没试能不能记忆化优化一下)
如果还不懂,请看代码讲解
代码实现:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <math.h>
#include <queue>
#include <string.h>
#define filename(a) freopen(a ".in", "r", stdin), freopen(a ".out", "w", stdout);
using namespace std;
template < typename T >
void quickin(T &a) {
a= 0;
T f= 1, c= getchar();
while(c < '0' || c > '9') {
if(c == '-') f= -1;
c= getchar();
}
while(c >= '0' && c <= '9') a= a * 10 + c - '0', c= getchar();
a= a * f;
return;
}
//考场上手打的读入,有点弱
int head[100001], fhead[100001], edptr, fedptr;
//链式前向星存储
struct edge {
int to;
int nexty;
} eds[1000001], feds[1000001];
//eds存正向边,feds存反向边
void add(int x, int y) {
edptr++;
eds[edptr].to= y;
eds[edptr].nexty= head[x];
head[x]= edptr;
fedptr++;
feds[fedptr].to= x;
feds[fedptr].nexty= fhead[y];
fhead[y]= fedptr;
}
bool canarrivensrc[100001], canarriven[100001], walkpast[100001];
//canarrivensrc 表示第 1 号城市是否可以到达某城市
//canarriven 表示某城市是否可以到达 n 号城市
//walkpast这个是canarrive函数中用的,记录从某城市是否可以到达某城市
bool canarrive(int _src, int _to) {
//canarrive函数是判断买入城市是否能到达卖出城市
memset(walkpast, 0, sizeof(walkpast));
queue< int > nodes;
walkpast[_src]= true;
nodes.push(_src);
while(!nodes.empty()) {
int nown= nodes.front();
nodes.pop();
for(int i= head[nown]; i; i= eds[i].nexty) {
int to= eds[i].to;
if(!walkpast[to]) {
walkpast[to]= true;
nodes.push(to);
}
}
}
return walkpast[_to];
}
void InitSPFA(int _src, int _fsrc) {
//在输出后调用
//处理canarrivensrc和canarriven
//正向跑和反向跑SPFA
queue< int > nodes;
canarrivensrc[_src]= true;
nodes.push(_src);
while(!nodes.empty()) {
int nown= nodes.front();
nodes.pop();
for(int i= head[nown]; i; i= eds[i].nexty) {
int to= eds[i].to;
if(!canarrivensrc[to]) {
canarrivensrc[to]= true;
nodes.push(to);
}
}
}
canarriven[_fsrc]= true;
nodes.push(_fsrc);
while(!nodes.empty()) {
int nown= nodes.front();
nodes.pop();
for(int i= fhead[nown]; i; i= feds[i].nexty) {
int to= feds[i].to;
if(!canarriven[to]) {
canarriven[to]= true;
nodes.push(to);
}
}
}
return;
}
int n, m, maxp= INT_MIN, minp= INT_MAX, maxpi, minpi, v[100001], tmpx, tmpy, tmpz, bans= 0;
//maxp和maxpi记录输入中最大价格和最大价格的城市,minp和minpi记录最小
//v记录所有城市的价格
//bans记录最优答案
double get_time() {
return clock() / (double)CLOCKS_PER_SEC;
}
const double BeginT= 1000, EndT= 1e-5, ChangeT= 0.98;
int tmpbegin, tmpend, tmpc;
void SA(int times) {
tmpbegin= minpi;
tmpend= maxpi;
//每次先选择差价最大的两个城市,不过自我感觉没用上啊
while(times--) {
for(double T= BeginT; T > EndT; T*= ChangeT) {
if(canarrivensrc[tmpbegin] && canarriven[tmpend] && canarrive(tmpbegin, tmpend)) {
//判断是否第 1 号城市能到达买入城市,是否卖出城市能到达第 n 号城市,是否买入城市能到达卖出城市
tmpc= v[tmpend] - v[tmpbegin];
if(tmpc > bans) {
bans= tmpc;
//更新答案
}
}
tmpbegin= rand() % n + 1;
tmpend= rand() % n + 1;
//重新随机选择城市,也可以加while(tmpbegin==tmpend);
}
}
//感觉是伪SA,不过结果都一样,考场上写的严格SA在此段代码后
}
int main() {
srand(time(0));
// filename("atree");
quickin(n), quickin(m);
if(n == 1) {
//特判
printf("0\n");
return 0;
}
for(int i= 1; i <= n; i++) {
quickin(v[i]);
if(v[i] > maxp) {
maxp= v[i];
maxpi= i;
}
if(v[i] < minp) {
minp= v[i];
minpi= i;
}
//输入时记录最大最小价格城市
}
for(int i= 1; i <= m; i++) {
quickin(tmpx), quickin(tmpy), quickin(tmpz);
add(tmpx, tmpy);
if(tmpz == 2) add(tmpy, tmpx);
}
InitSPFA(1, n);
//初始化
while(get_time() < 0.62) {
//卡时(不过用处不大)
SA(1);
}
printf("%d\n", bans);
return 0;
}
较为严格的SA(其实结果都一样):
for(double T= BeginT; T > EndT; T*= ChangeT) {
if(canarrivensrc[tmpbegin] && canarriven[tmpend] && canarrive(tmpbegin, tmpend)) {
tmpc= v[tmpend] - v[tmpbegin];
if(tmpc > bans) {
bans= tmpc;
}
else if(exp((tmpc - bans) / T) < (double)rand() / RAND_MAX) {
//根据温度大小随机接受此次较差解
if(rand() % 2) {
//随机改变买入城市或卖出城市其中一个
do {
tmpend= rand() % n + 1;
} while(tmpbegin == tmpend);
}
else {
do {
tmpbegin= rand() % n + 1;
} while(tmpbegin == tmpend);
}
}
else {
//不接受此次较差解
do {
tmpbegin= rand() % n + 1;
tmpend= rand() % n + 1;
} while(tmpbegin == tmpend);
}
}
else {
//这三个城市连接不了,随机更改
do {
tmpbegin= rand() % n + 1;
tmpend= rand() % n + 1;
} while(tmpbegin == tmpend);
}
}
这样严格的SA似乎判断多了会变慢(其实是考场上随便写的)
更多废话:
这个数据还是不那么毒瘤,但是不开O2就会又WA又TLE,开了怎么都能过...
拿小号试了很长时间,怎么设参数和卡时,只要不开O2都有WA或者TLE,真的是WAWA大哭...
不开O2用模拟退火能过的大佬真的太神了!
评测信息(开O2)(卡时限0.62s):
Accepted 100
用时: 6153ms / 内存: 9372KB