TLE on 70
查看原帖
TLE on 70
511676
naoliaok_lovely楼主2025/6/17 15:06

我的 isap 板子不会是错的吧()

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 8 * N;
namespace Flow
{
	int h[N], ne[M], e[M], w[M], idx = 1;
	void add(int a, int b, int c)
	{
		e[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
	}
	void add1(int a, int b, int c)
	{
		add(a, b, c), add(b, a, 0);
	}
	
	int tot, s, t;
	int dis[N], cnt[N], cur[N];
	int sap(int x, int inflow)
	{
		if(x == t) return inflow;
		int outflow = 0;
		for(int &i = cur[x]; i; i = ne[i])
			if(w[i] && dis[x] == dis[e[i]] + 1)
			{
				int flow = sap(e[i], min(inflow - outflow, w[i]));
				w[i] -= flow, w[i ^ 1] += flow, outflow += flow;
				if(inflow == outflow || dis[s] >= tot) return outflow; 
			}
		if(!--cnt[dis[x]]) dis[s] = tot;
		cnt[++dis[x]]++, cur[x] = h[x];
		return outflow;
	}
	
	int maxflow()
	{
		int ans = 0;
		while(dis[s] < tot) ans += sap(s, INT_MAX);
		return ans;
	}
	
	void clear()
	{
		memset(h, 0, sizeof(h)), idx = 1;
		memset(dis, 0, sizeof(dis));
		memset(cnt, 0, sizeof(cnt));
	}
}
int n, m, c[N], ans[N];
vector<vector<int> > a; 
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
char dc[] = {'R', 'L', 'U', 'D'};

inline int get(int x, int y)
{
	return (x - 1) * m + y;
}

int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		Flow::clear();
		
		scanf("%d%d", &n, &m);
		a.resize(n + 10);
		for(int i = 0; i < n + 10; i++) a[i].resize(m + 10);
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				scanf("%d", &a[i][j]);
		
		Flow::tot = n * m + 4, Flow::s = n * m + 3, Flow::t = n * m + 4;
		int res = 0;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
			{
				if(i > 1 && a[i][j] == a[i - 1][j])
				{
					if(i + j & 1) Flow::add1(get(i, j), get(i - 1, j), 1);
					else Flow::add1(get(i - 1, j), get(i, j), 1);
				}
				if(j > 1 && a[i][j] == a[i][j - 1])
				{
					if(i + j & 1) Flow::add1(get(i, j), get(i, j - 1), 1);
					else Flow::add1(get(i, j - 1), get(i, j), 1);
				}
				
				bool flag = 1;
				for(int k = 0; k <= 3; k++)
				{
					int x = i + dx[k], y = j + dy[k];
					if(1 <= x && x <= n && 1 <= y && y <= m && a[x][y] < a[i][j])
						flag = 0;
				}
				if(flag)//must match
				{
					if(i + j & 1) Flow::add1(n * m + 3, get(i, j), 1), Flow::add1(n * m + 1, n * m + 4, 1);
					else Flow::add1(n * m + 3, n * m + 2, 1), Flow::add1(get(i, j), n * m + 4, 1);
					res++;
				}
				else
				{
					if(i + j & 1) Flow::add1(n * m + 1, get(i, j), 1);
					else Flow::add1(get(i, j), n * m + 2, 1);
				}
			}
		Flow::add(n * m + 2, n * m + 1, 1e9);
		
		memcpy(Flow::cur, Flow::h, sizeof(Flow::cur));
		if(Flow::maxflow() != res)
		{
			puts("NO");
			continue;
		}
		
		puts("YES");
		memset(c, 0, sizeof(c));
		for(int i = 1; i <= n * m; i++)
			for(int j = Flow::h[i]; j; j = Flow::ne[j])
				if(j & 1 ^ 1 && !Flow::w[j])
				{
					int k = Flow::e[j];
					if(k <= n * m)
					{
						if(abs(i - k) == 1 && m > 1) c[min(i, k)] = 'R', c[max(i, k)] = 'L';
						else c[min(i, k)] = 'D', c[max(i, k)] = 'U';
						ans[i] = 1, ans[k] = a[(i - 1) / m + 1][(i - 1) % m + 1] - 1;
					}
				}
		
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				if(!c[get(i, j)])
					for(int k = 0; k <= 3; k++)
					{
						int x = i + dx[k], y = j + dy[k];
						if(1 <= x && x <= n && 1 <= y && y <= m && a[x][y] < a[i][j])
							ans[get(i, j)] = a[i][j] - a[x][y], c[get(i, j)] = dc[k];
					}
				printf("%d ", ans[get(i, j)]);
			}
			puts("");
		}
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
				printf("%c ", c[get(i, j)]);
			puts("");
		}
	}
	return 0;
}
2025/6/17 15:06
加载中...