oj.uz

답안 #528710

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528710 2022-02-21T07:29:46 Z colazcy Domino (COCI15_domino) C++17
0 / 160
 11 ms 16208 KB 
#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];
		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;
}

Compilation message

domino.cpp: In function 'int main()':
domino.cpp:77:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  std::freopen("fufu.in","r",stdin);
      |  ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 16168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 16100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 16112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 16208 KB Output isn't correct
2 Halted 0 ms 0 KB -