|

楼主 |
发表于 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;
- }
复制代码 |
-
|