社区讨论

求大佬帮忙

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 条回复,欢迎继续交流。

正在加载回复...