POJ 3041 Asteroids(최소 덮어쓰기)
1342 단어 도론-이분도 일치
POJ 3041 Asteroids
제목 링크
제목: 바둑판 위에 물건을 놓으면 가장 적은 행렬을 선택해서 이 물건들을 제거할 수 있도록 요구한다.
사고방식: 매우 고전적인 물문제, 행렬에 물건의 가장자리가 있다. 그리고 가장 작은 점으로 덮어쓰면 답이 나온다. 가장 작은 점으로 덮어쓰면 가장 큰 일치와 같다.
코드:#include
#include
#include
#include
using namespace std;
const int N = 505;
int n, m;
vector g[N];
int left[N], vis[N];
bool dfs(int u) {
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (vis[v]) continue;
vis[v] = 1;
if (!left[v] || dfs(left[v])) {
left[v] = u;
return true;
}
}
return false;
}
int hungary() {
int ans = 0;
memset(left, 0, sizeof(left));
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
if (dfs(i)) ans++;
}
return ans;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
int x, y;
for (int i = 1; i <= n; i++) g[i].clear();
while (m--) {
scanf("%d%d", &x, &y);
g[x].push_back(y);
}
printf("%d
", hungary());
}
return 0;
}
#include
#include
#include
#include
using namespace std;
const int N = 505;
int n, m;
vector g[N];
int left[N], vis[N];
bool dfs(int u) {
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (vis[v]) continue;
vis[v] = 1;
if (!left[v] || dfs(left[v])) {
left[v] = u;
return true;
}
}
return false;
}
int hungary() {
int ans = 0;
memset(left, 0, sizeof(left));
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
if (dfs(i)) ans++;
}
return ans;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
int x, y;
for (int i = 1; i <= n; i++) g[i].clear();
while (m--) {
scanf("%d%d", &x, &y);
g[x].push_back(y);
}
printf("%d
", hungary());
}
return 0;
}