社区讨论
求大佬帮忙
P2045方格取数加强版参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6uzlal
- 此快照首次捕获于
- 2025/11/20 11:15 4 个月前
- 此快照最后确认于
- 2025/11/20 11:15 4 个月前
这份代码改了一晚上, 第九个点要么T要么WA... QAQ
感觉没什么问题啊,求大佬查错.. 代码也不长, 变量名也很清真...
CPP#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 100005
#define INF 99999999
template <class TT>
IN void in(TT &x)
{
x = 0; R char c = gc;
W (!isdigit(c)) c = gc;
W (isdigit(c))
x = (x << 1) + (x << 3) + c - 48, c = gc;
}
int siz, hd, tl, tim, base, S, T, cnt = -1;
int head[MX], del[MX], dis[MX], que[MX], pre[MX], mp[55][55];
bool vis[MX];
long long ans;
IN int getid(const int &hang, const int &lie)
{return (hang - 1) * siz + lie;}
struct Edge
{int to, flow, cost, nex;} edge[MX << 1];
IN void addedge(const int &from, const int &to, const int &fl, const int &cost)
{
edge[++cnt] = {to, fl, cost, head[from]}; head[from] = cnt;
edge[++cnt] = {from, 0, -cost, head[to]}; head[to] = cnt;
}
IN bool SPFA()
{
que[hd = tl = 1] = S;
std::memset(dis, 63, sizeof(dis));
std::memset(del, 63, sizeof(del));
std::memset(vis, false, sizeof(vis));
dis[S] = 0; R int now; pre[T] = -1;
W (hd >= tl)
{
now = que[tl++];
for (R int i = head[now]; ~i; i = edge[i].nex)
{
if(dis[edge[i].to] > dis[now] + edge[i].cost && edge[i].flow > 0)
{
dis[edge[i].to] = dis[now] + edge[i].cost;
del[edge[i].to] = std::min(del[now], edge[i].flow);
pre[edge[i].to] = i;
if(!vis[edge[i].to]) vis[edge[i].to] = true, que[++hd] = edge[i].to;
}
}
vis[now] = false;
}
return pre[T] >= 0;
}
void updata()
{
ans += del[T] * dis[T];
R int now = T, pr = 0;
W (now != S)
{
pr = pre[now];
edge[pr].flow -= del[T];
edge[pr ^ 1].flow += del[T];
now = edge[pr ^ 1].to;
}
}
int main(void)
{
in(siz); in(tim); base = siz * siz;
int id; S = 0, T = (base << 1) + 1;
std::memset(head, -1, sizeof(head));
addedge(S, 1, tim, 0); addedge(base << 1, T, tim, 0);
for (R int i = 1; i <= siz; ++i)
for (R int j = 1; j <= siz; ++j)
{
in(mp[i][j]);
id = getid(i, j);
addedge(id, id + base, 1, -mp[i][j]);
addedge(id, id + base, INF, 0);
if(i != siz) addedge(id + base, id + siz, INF, 0);
if(j != siz) addedge(id + base, id + 1, INF, 0);
}
W (SPFA()) updata();
printf("%lld", -ans);
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...