关于码风
  • 板块灌水区
  • 楼主JWRuixi
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/8/4 18:37
  • 上次更新2023/10/27 17:01:22
查看原帖
关于码风
317495
JWRuixi楼主2022/8/4 18:37
#include <bits/stdc++.h>
#define int long long
#define maxn 1005
using namespace std;
const int inf = 1e18;
int val[maxn][maxn], tot, head[maxn * maxn], dep[maxn * maxn], n, m, S, T, rght[maxn];
struct noded {
	int x, y;
};
vector <noded> vec[maxn * maxn];
queue<int> Q;
struct node {
	int v, pre, w;
}e[maxn << 1];
void add(int u, int v, int w) {
	e[++ tot].v = v;
	e[tot].w = w;
	e[tot].pre = head[u];
	head[u] = tot;
}
bool bfs() {
	for(int i = 0;i <= n * m + 1;i++) dep[i] = 0;
	dep[S] = 1;
	Q.push(S);
	while(!Q.empty()) {
		int t = Q.front();
		Q.pop();
		for(int i = head[t];i;i = e[i].pre) {
			int v = e[i].v;
			if(!dep[v] && e[i].w) {
				dep[v] = dep[t] + 1;
				Q.push(v);
			}
		}
	}
	return dep[T];
}
int dfs(int now, int flow) {
	if(now == T) return flow;
	int out = 0;
	for(int i = head[now];i && flow;i = e[i].pre) {
		int v = e[i].v;
		if(dep[v] == dep[now] + 1 && e[i].w) {
			int res = dfs(v, min(flow, e[i].w));
			out += res, flow -= res;
			e[i].w -= res, e[i ^ 1].w += res;
		}
	}
	if(out == 0) dep[now] = 0;
	return out;
}
int id(int x, int y) {
	return (x - 1) * m + y;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
}signed main() {//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	scanf("%lld%lld", &n, &m);//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	int t = 0;
	S = 0, T = n * m + 1;
	for(int i = 1;i <= n;i++) {
		for(int j = 1, k;j <= m;j++) {
			scanf("%lld%lld", &val[i][j], &k);
			for(int l = 1, x, y;l <= k;l++) {
				scanf("%lld%lld", &x, &y);
				x ++, y ++;
				vec[id(i, j)].push_back({x, y});
				if(x == i && y > j) rght[i] = max(rght[i], y);
			}
		}
	}
	for(int i = 1;i <= n;i++) {
		for(int j = rght[i] + 1;j <= m;j++) {
			if(val[i][j] > 0) {
				t += val[i][j];
				add(S, id(i, j), val[i][j]);
				add(id(i, j), S, 0);
			}
			else {
				add(id(i, j), T, -val[i][j]);
				add(T, id(i, j), 0);
			}
			for(int k = 0;k < vec[id(i, j)].size();k++) {
				int x = vec[id(i, j)][k].x, y = vec[id(i, j)][k].y;
				add(id(x, y), id(i, j), inf);
				add(id(i, j), id(x, y), 0);
			}
			
		}
	}
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m - 1;j++) {
			add(id(i, j), id(i, j + 1), inf);
			add(id(i, j + 1), id(i, j), 0);
		}
	}
	for(int i = 1;i <= n;i++) {
		
	}
	int ans = 0;
	while(bfs()) ans += dfs(S, inf + 114514);
	printf("%lld\n", t - ans);
}

请重点关注标记感叹号的第54行。 请问如何评价这种行为。

2022/8/4 18:37
加载中...