ISAP 超时求优化/kel
  • 板块P4313 文理分科
  • 楼主CEFqwq
  • 当前回复8
  • 已保存回复9
  • 发布时间2025/2/7 09:09
  • 上次更新2025/2/7 11:40:40
查看原帖
ISAP 超时求优化/kel
482610
CEFqwq楼主2025/2/7 09:09
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[50005], d[50005], qq[50005], qb[50005];
int w[50005], hsh[50005], sum, tn;
struct node{
	int v, c, id;
};
vector<node> G[50005];
int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};
int ans, mxf, ttmp;
int m, n, s, t, u, mn, hj;
bool fl;
void addedge(int u, int v, int c){
	G[u].push_back({v, c, G[v].size()});
	G[v].push_back({u, 0, G[u].size() - 1});
}
int toid(int x, int y){
	return (x - 1) * m + y;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin >> n >> m;
    s = n * m + 1;
    t = n * m + 2;
	tn = n * m + 2;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			int x;
			cin >> x;
			sum += x;
			addedge(s, toid(i, j), x);
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			int x;
			cin >> x;
			sum += x;
			addedge(toid(i, j), t, x);
		}
	for (int ii = 1; ii <= n; ii++)
		for (int jj = 1; jj <= m; jj++){
			int x;
			cin >> x;
			sum += x;
			addedge(s, tn + 1, x);
			for (int fx = 0; fx <= 4; fx++){
				if (ii + dx[fx] < 1 || ii + dx[fx] > n || jj + dy[fx] < 1 || jj + dy[fx] > m)
					continue;
				addedge(tn + 1, toid(ii + dx[fx], jj + dy[fx]), 0xCEF5201314);
			}
			++tn;
		}
	for (int ii = 1; ii <= n; ii++)
		for (int jj = 1; jj <= m; jj++){
			int x;
			cin >> x;
			sum += x;
			addedge(tn + 1, t, x);
			for (int fx = 0; fx <= 4; fx++){
				if (ii + dx[fx] < 1 || ii + dx[fx] > n || jj + dy[fx] < 1 || jj + dy[fx] > m)
					continue;
				addedge(toid(ii + dx[fx], jj + dy[fx]), tn + 1, 0xCEF5201314);
			}
			++tn;
		}
	n = tn;
    hsh[0] = n;
    for (int i = 1; i <= n; i++)
		p[i] = 1;
    u = s;
    mxf = INT_MAX;
    while (d[s] < n){
        w[u] = mxf;
        fl = 0;
        for (int i = 0; i < G[u].size(); i++){
        	auto tmp = G[u][i];
        	int v = tmp.v, c = tmp.c, id = tmp.id;
            if (c > 0 && d[u] == d[v] + 1){
                fl = 1;
                p[u] = v;
                if (c < mxf)
					mxf = c;
                qq[v] = u;
                qb[v] = i;
                u = v;
                if (u == t){
                    ans += mxf;
                    while (u != s){
                        ttmp = u;
                        u = qq[u];
                        G[u][qb[ttmp]].c -= mxf;
                        G[ttmp][G[u][qb[ttmp]].id].c += mxf;
                    }
                    mxf = LLONG_MAX;
                }
                break;
            }
        }
        if (fl)
			continue;
        mn = n - 1;
        for (auto tmp : G[u])
            if (tmp.c && d[tmp.v] < mn)
                hj = tmp.v, mn = d[tmp.v];
        p[u] = hj;
        hsh[d[u]]--;
        if (!hsh[d[u]])
			break;
        d[u] = mn + 1;
        hsh[d[u]]++;
        if (u != s){
        	u = qq[u];
        	mxf = w[u];
		}
    }
    cout << sum - ans;
    return 0;
}
2025/2/7 09:09
加载中...