Submission #528711

#	Time	Username	Problem	Language	Result	Execution time	Memory
528711		colazcy	Domino (COCI15_domino)	C++17	130 / 160	2271 ms	172856 KiB

domino

#include <iostream>
#include <queue>
#include <algorithm>
#include <cassert>
#include <cstring>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 2e3 + 10,dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
namespace mcmf{
	constexpr int maxn = 233,maxm = 2333,inf = 0x3f3f3f3f;
	struct Edge{
		int u,v,cap,cost;
	}edges[maxm];
	int head[maxn],nxt[maxm],tot = 1;
	void addedge(const int u,const int v,const int cap,const int cost){
		// debug("%d %d %d %d\n",u,v,cap,cost);
		edges[++tot] = Edge{u,v,cap,cost};
		nxt[tot] = head[u];
		head[u] = tot;
		edges[++tot] = Edge{v,u,0,-cost};
		nxt[tot] = head[v];
		head[v] = tot;
	}
	std::queue<int> q;
	int a[maxn],d[maxn],pre[maxn];
	bool inq[maxn];
	bool spfa(const int s,const int t,int &flow,int &cost){
		std::fill(a + 1,a + 1 + t,-1);
		std::fill(d + 1,d + 1 + t,-inf);
		q.push(s); inq[s] = true;
		a[s] = 0x3f3f3f3f; d[s] = 0;
		while(!q.empty()){
			let u = q.front(); q.pop(),inq[u] = false;
			for(int i = head[u];i;i = nxt[i]){
				let &[u,v,cap,cost] = edges[i];
				if(cap && d[u] + cost > d[v]){
					d[v] = d[u] + cost;
					a[v] = std::min(cap,a[u]);
					pre[v] = i;
					if(!inq[v])q.push(v),inq[v] = true;
				}
			}
		}
		if(a[t] == -1)return false;
		let f = a[t],c = d[t];
		if(c < 0)return false;
		flow += f;
		cost += f * c;
		for(int i = pre[t];i;i = pre[edges[i].u])
			edges[i].cap -= f,
			edges[i ^ 1].cap += f;
		return true;
	}
	std::pair<int,int> mcmf(const int s,const int t){
		std::pair<int,int> res;
		while(spfa(s,t,res.first,res.second));
		return res;
	}
}
ll sum;
bool valid[maxn][maxn];
int n,k,tot,val[maxn][maxn],encode[maxn][maxn],col[maxn][maxn];
std::vector<std::pair<std::pair<int,int>,std::pair<int,int>>> seq;
bool chk(const int x,const int y){return x >= 1 && x <= n && y >= 1 && y <= n;}
void dfs(const int x,const int y){
	for(int i = 0;i < 4;i++){
		let nx = x + dx[i],ny = y + dy[i];
		if(valid[nx][ny] && col[nx][ny] == -1)col[nx][ny] = col[x][y] ^ 1,dfs(nx,ny);
	}
}
int main(){
// #ifndef ONLINE_JUDGE
// 	std::freopen("fufu.in","r",stdin);
// #endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n >> k;
	rep(i,1,n)
		rep(j,1,n)
			std::cin >> val[i][j],sum += val[i][j];
	seq.reserve(n * n);
	rep(x,1,n - 1)
		rep(y,1,n - 1)
			seq.emplace_back(std::make_pair(x,y),std::make_pair(x,y + 1)),
			seq.emplace_back(std::make_pair(x,y),std::make_pair(x + 1,y));
	std::sort(seq.begin(),seq.end(),[](let &a,let &b){
		return 	val[a.first.first][a.first.second] + val[a.second.first][a.second.second] >
				val[b.first.first][b.first.second] + val[b.second.first][b.second.second];
	});
	// rep(x,1,n)
		// rep(y,1,n)
			// valid[x][y] = true;
	for(int i = 0;i < 7 * k - 6 && i < (int)seq.size();i++){
		let [x1,y1] = seq[i].first;
		let [x2,y2] = seq[i].second;
		valid[x1][y1] = valid[x2][y2] = true;
	}
	// rep(x,1,n)
		// rep(y,1,n)
			// if(valid[x][y])debug("%d %d\n",x,y);
	std::memset(col,-1,sizeof(col));
	rep(x,1,n)
		rep(y,1,n)
			if(valid[x][y] && col[x][y] == -1)
				col[x][y] = 0,
				dfs(x,y);
	int tot = 0;
	rep(x,1,n)
		rep(y,1,n)
			if(valid[x][y])encode[x][y] = ++tot;
	let s = ++tot,t = ++tot;
	rep(x,1,n)
		rep(y,1,n)
			if(valid[x][y]){
				if(col[x][y] == 0){
					mcmf::addedge(s,encode[x][y],1,val[x][y]);
					for(int i = 0;i < 4;i++){
						let nx = x + dx[i],ny = y + dy[i];
						if(col[nx][ny] == 1)
							mcmf::addedge(encode[x][y],encode[nx][ny],1,0);
					}
				}else if(col[x][y] == 1)mcmf::addedge(encode[x][y],t,1,val[x][y]);
			}
	let ss = ++tot;
	mcmf::addedge(ss,s,k,0);
	let [flow,cost] = mcmf::mcmf(ss,t);
	std::cout << sum - cost << "\n";	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10
• Subtask 16: 10 / 10