|
楼主 |
发表于 2021-8-4 17:42:22
|
显示全部楼层
本帖最后由 一世轻尘 于 2021-8-4 17:44 编辑
这是数学建模国赛一等奖的代码,太复杂了,看懂估计要花费很长时间,代码的思路没有问题,而且作者在比赛的时候确实跑出了正确的结果,正常报错的话,会提示是在代码哪一行出的问题,这个报错确实应该跟源代码没啥关系,处理过类似问题的人应该能很快知道是在哪里有问题#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
struct sta
{
short d, i, w, f;
sta(short _d = 0, short _i = 0, short _w = 0, short _f = 0)
{
d = _d, i = _i, w = _w, f = _f;
}
bool check()
{
return !d && !i && !w && !f;
}
void Print()
{
printf("%d %d %d %d\n", d, i, w, f);
}
};
const int D = 30;
const int N = 64;
const int W = 400;
const int F = 600;
const int Heavy = 1200;
const int start_money = 10000;
int n, m, dis[N + 1][N + 1];
short dp[D + 1][N + 1][W + 1][F + 1];
sta last[D + 1][N + 1][W + 1][F + 1];
bool vis[D + 1][N + 1][W + 1][F + 1];
vector<int> q[N + 1];
int weather[D + 1];
queue<sta> que;
int l, r;
void bfs()
{
for (int w = 0; w <= W; w++)
for (int f = 0; 3 * w + 2 * f <= Heavy && 5 * w + 10 * f <= start_money && f <= F; f++)
{
dp[0][1][w][f] = start_money - 5 * w - 10 * f;
que.push(sta(0, 1, w, f));
//sta(0,1,w,f).Print();
vis[0][1][w][f] = 1;
r++;
}
while (!que.empty())
{
//printf("%.8f\n",1.0*l/(1ll*D*W*F*W*F));
sta now = que.front();
que.pop();
//now.Print();
int cw = 0, cf = 0, d = now.d, i = now.i, w = now.w, f = now.f, k;
vis[d][i][w][f] = 0;
if (d + 1 > D)
continue;
if (i == 64)
continue;
switch (weather[d + 1])
{
case 1:
{
cw = 5, cf = 7;
break;
}
case 2:
{
cw = 8, cf = 6;
break;
}
case 3:
{
cw = 10, cf = 10;
break;
}
}
if ((i == 30 || i == 55) && w >= 3 * cw && f >= 3 * cf && dp[d + 1][i][w - 3 * cw][f - 3 * cf] < dp[d][i][w][f] + 1000)
{
dp[d + 1][i][w - 3 * cw][f - 3 * cf] = dp[d][i][w][f] + 1000;
last[d + 1][i][w - 3 * cw][f - 3 * cf] = sta(d, i, w, f);
if (!vis[d + 1][i][w - 3 * cw][f - 3 * cf])
{
vis[d + 1][i][w - 3 * cw][f - 3 * cf] = 1;
que.push(sta(d + 1, i, w - 3 * cw, f - 3 * cf));
//sta(d+1,i,w-3*cw,f-3*cf).Print();
r++;
}
}
if (weather[d + 1] != 3 && w >= 2 * cw && f >= 2 * cf)
{
for (auto u : q[i])
if (dp[d + 1][u][w - 2 * cw][f - 2 * cf] < dp[d][i][w][f])
{
dp[d + 1][u][w - 2 * cw][f - 2 * cf] = dp[d][i][w][f];
last[d + 1][u][w - 2 * cw][f - 2 * cf] = sta(d, i, w, f);
if (!vis[d + 1][u][w - 2 * cw][f - 2 * cf])
{
vis[d + 1][u][w - 2 * cw][f - 2 * cf] = 1;
que.push(sta(d + 1, u, w - 2 * cw, f - 2 * cf));
//sta(d+1,u,w-2*cw,f-2*cf).Print();
r++;
}
}
}
if (i == 39 || i == 62)
{
for (int w1 = 0; w1 * 3 <= Heavy - w * 3 - f * 2 && w1 * 10 <= dp[d][i][w][f] && w1 + w <= W; w1++)
for (int
f1 = 0;
(w1 + w) * 3 + (f1 + f) * 2 <= Heavy && w1 * 10 + f1 * 20 <= dp[d][i][w][f] && f1 + f <= F; f1++)
if (dp[d][i][w + w1][f + f1] < dp[d][i][w][f] - (w1 * 10 + f1 * 20))
{
dp[d][i][w + w1][f + f1] = dp[d][i][w][f] - (w1 * 10 + f1 * 20);
last[d][i][w + w1][f + f1] = sta(d, i, w, f);
if (!vis[d][i][w + w1][f + f1])
{
vis[d][i][w + w1][f + f1] = 1;
que.push(sta(d, i, w + w1, f + f1));
//sta(d,i,w+w1,f+f1).Print();
r++;
}
}
}
if (w >= cw && f >= cf && dp[d + 1][i][w - cw][f - cf] < dp[d][i][w][f])
{
dp[d + 1][i][w - cw][f - cf] = dp[d][i][w][f];
last[d + 1][i][w - cw][f - cf] = sta(d, i, w, f);
if (!vis[d + 1][i][w - cw][f - cf])
{
vis[d + 1][i][w - cw][f - cf] = 1;
que.push(sta(d + 1, i, w - cw, f - cf));
//sta(d+1,i,w-cw,f-cf).Print();
r++;
}
}
}
}
void getans(int d, int i, int w, int f)
{
sta u = last[d][i][w][f];
if (!u.check())
getans(u.d, u.i, u.w, u.f);
printf("%d %d %d %d\n", d, i, w, f);
}
int main()
{
cin >> n >> m;
memset(dp, -1, sizeof(dp));
for (int a, b, i = 1; i <= m; i++)
{
cin >> a >> b;
dis[a][b] = 1, q[a].push_back(b);
}
for (int i = 1; i <= 30; i++)
cin >> weather[i];
bfs();
int T = 64;
sta ans(0, T, 0, 0);
double aaans = 0;
for (int d = 0; d <= 30; d++)
for (int w = 0; w <= W; w++)
for (int f = 0; f <= F; f++)
if (dp[d][T][w][f] != -1 && 1.0 * dp[d][T][w][f] + w * 2.5 + f * 5 > 1.0 * dp[ans.d][ans.i][ans.w][ans.f] + ans.w * 2.5 + ans.f * 5)
ans = sta(d, T, w, f), aaans = 1.0 * dp[d][T][w][f] + w * 2.5 + f * 5;
cout << aaans << "\n";
for (int d = 0; d <= 30; d++)
for (int w = 0; w <= W; w++)
for (int f = 0; f <= F; f++)
if ((int)(1.0 * dp[d][T][w][f] + ans.w * 2.5 + ans.f * 5) == aaans)
{
getans(d, T, w, f);
puts("==================");
}
return 0;
}
|
-
|