POJ 2446 Chessboard(다이어그램 일치)
제목: n*m의 바둑판을 드리겠습니다. 위에 구멍이 있습니다. 약간의 1*2의 널빤지를 놓아야 합니다. 구멍의 위치는 놓을 수 없습니다. 다른 위치는 모두 덮어야 합니다. 임의의 칸은 두 개의 널빤지를 동시에 덮을 수 없습니다. 완전히 덮을 수 있는지 확인하세요.
사고방식: 이분도 일치.두 칸과 인접하고 행수 + 열수는 틀림없이 하나의 홀수와 짝수일 것이다. 이로써 칸을 두 파로 나누어 일치시키면 된다.최대 흐름을 사용할 수 있지만 헝가리 알고리즘이 더 빠르고 코드가 짧다.
자세한 참고 코드:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 1500;
int T,n,m,k;
vector<int> g[maxn];
int from[maxn], tot, x, y;
bool use[maxn];
bool match(int x) {
int len = g[x].size();
for(int i = 0; i < len; i++)
if(!use[g[x][i]]) {
use[g[x][i]] = true;
if(from[g[x][i]] == -1 || match(from[g[x][i]])) {
from[g[x][i]] = x;
return true;
}
}
return false;
}
int hungary(int n) {
tot = 0;
memset(from, -1, sizeof(from));
for(int i = 1; i <= n; i++) {
memset(use, 0, sizeof(use));
if(match(i)) ++tot;
}
return tot;
}
int getid(int r, int c) {
return (r - 1) * m + c;
}
bool vis[55][55];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int main() {
while(~scanf("%d%d%d",&n,&m,&k)) {
memset(vis, false, sizeof(vis));
for(int i = 0; i < k; i++) {
scanf("%d%d",&x,&y);
vis[y][x] = true;
}
int res = n * m - k;
if(res & 1) {
printf("NO
");
continue;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(vis[i][j]) continue;
int id1 = getid(i, j);
if((i + j) & 1) continue;
for(int l = 0; l < 4; l++) {
int x = i + dx[l];
int y = j + dy[l];
if(x < 1 || x > n || y < 1 || y > m || vis[x][y]) continue;
int id2 = getid(x, y);
g[id1].push_back(id2);
}
}
}
int ans = hungary(n * m);
if(ans == res / 2) printf("YES
");
else printf("NO
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.