> kdoctor
Environment diagnose (to see all details, use -v option):
[✓] Operation System
[✓] Java
[✓] Android Studio
[✓] Xcode
[✖] Cocoapods
✖ cocoapods not found
Get cocoapods from https://guides.cocoapods.org/using/getting-started.html#installation
// x축 정렬을 하는 이유 ?
// x축 정렬을 통해 x의축의 차이만으로 최대값 후보에서 여러 점들을 제외 시킬 수 있다.
sort(vec.begin(), vec.end());
// {y,x}으로 insert한 이유?
// dx를 통해 if문으로 x축과의 거리는 처리 하였고,
// map에 남아잇는 점들중에서 y축으로 lower_bound, upper_bound를 하기 위함이다.
// = 0 인이 이유?
// 어떤 값이든 크게 상관없지만 , INF보단 작고, -INF보단 커야한다.( lower_bound, upper_bound를 위해 )
m[{vec[0].second, vec[0].first}] = 0;
m[{vec[1].second, vec[1].first}] = 0;
ll ans = getDist(vec[0], vec[1]);
< 후보를 추가, 제외하면서 탐색 >
int pos = 0;
for (int i = 2; i < n; i++) {
// pos부터 i-1번까지 i번째점과 비교를 한다.
while (pos < i) {
// x축간의 거리 차이
int dx = vec[i].first - vec[pos].first;
// pos( i 점 기준으로 현재 map 있는 가장 왼쪽 점 ) 과 i번째 점간의 x축 거리가
// 더 작다면 pos점은 여전히 후보에 포함될 수 있다.
if (dx * dx <= ans) break;
// pos(i 점 기준으로 현재 map 있는 가장 왼쪽 점) 과 i번째 점간의 x축 거리가
// 더 크다면 pos점은 더이상 더 작은 ans값을 만들어내지 못한다.( 후보에서 제외된다 )
m.erase({ vec[pos].second,vec[pos].first });
pos++;
}
// getDist 는 sqrt를 없이 반환했음으로...
ll dis = sqrt(ans);
// map에 남아있는 점들중에서
// 현재 ans보다 작아 질 수 있는 후보 점들을 확인 하기위해 left, right를 찾고
auto left = m.lower_bound({ vec[i].second - dis, -INF });
auto right = m.upper_bound({ vec[i].second + dis, INF });
// ans 갱신
for (auto l = left; l != right; l++) {
ans = min(ans, getDist( {l->first.second,l->first.first}, vec[i]));
}
// i번째점은 당연히 뒤에 확인할게 있음으로 후보 점이 된다.
m[{vec[i].second, vec[i].first}] = 0;
}
그림으로 보나, 코드로 보나 쉽게 이해가 가지 않을 수 있을 것 같습니다.
때문에 중간 중간 주석으로, 과정에대해서 나름 상세하게 설명해 보았습니다.
전체코드
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <limits.h>
using namespace std;
#define INF INT_MAX
typedef long long ll;
// 문제에서 요구하는 거리는 거리의 제곱이기 때문에 sqrt를 사용하지 않았습니다.
ll getDist(pair<int,int> a, pair<int,int> b)
{
int x1 = a.first;
int y1 = a.second;
int x2 = b.first;
int y2 = b.second;
return (x2-x1)*(ll)(x2 - x1) + (y2-y1)*(ll)(y2-y1);
}
vector<pair<int, int>> vec;
map<pair<int, int>, int> m;
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n;
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
vec.push_back({ x,y });
}
// x축 정렬을 하는 이유 ?
// x축 정렬을 통해 x의축의 차이만으로 최대값 후보에서 여러 점들을 제외 시킬 수 있다.
sort(vec.begin(), vec.end());
// {y,x}으로 insert한 이유?
// dx를 통해 if문으로 x축과의 거리는 처리 하였고,
// map에 남아잇는 점들중에서 y축으로 lower_bound, upper_bound를 하기 위함이다.
// = 0 인이 이유?
// 어떤 값이든 크게 상관없지만 , INF보단 작고, -INF보단 커야한다.( lower_bound, upper_bound를 위해 )
m[{vec[0].second, vec[0].first}] = 0;
m[{vec[1].second, vec[1].first}] = 0;
ll ans = getDist(vec[0], vec[1]);
// pos = 0 부터, i = 2 부터인 이유?
// 편의상 첫번째점과 두번째점을 (x축 정렬 기준 ) 을 기준으로 잡았다.
// 밑의 코드의 for문을 돌리는대신 기준을 잡았다고 보면 된다.
/*
for(int i = 0 ; i < 2; i ++){
...
}
*/
int pos = 0;
for (int i = 2; i < n; i++) {
// pos부터 i-1번까지 i번째점과 비교를 한다.
while (pos < i) {
// x축간의 거리 차이
int dx = vec[i].first - vec[pos].first;
// pos( i 점 기준으로 현재 map 있는 가장 왼쪽 점 ) 과 i번째 점간의 x축 거리가
// 더 작다면 pos점은 여전히 후보에 포함될 수 있다.
if (dx * dx <= ans) break;
// pos(i 점 기준으로 현재 map 있는 가장 왼쪽 점) 과 i번째 점간의 x축 거리가
// 더 크다면 pos점은 더이상 더 작은 ans값을 만들어내지 못한다.( 후보에서 제외된다 )
m.erase({ vec[pos].second,vec[pos].first });
pos++;
}
// getDist 는 sqrt를 없이 반환했음으로...
ll dis = sqrt(ans);
// map에 남아있는 점들중에서
// 현재 ans보다 작아 질 수 있는 후보 점들을 확인 하기위해 left, right를 찾고
auto left = m.lower_bound({ vec[i].second - dis, -INF });
auto right = m.upper_bound({ vec[i].second + dis, INF });
// ans 갱신
for (auto l = left; l != right; l++) {
ans = min(ans, getDist( {l->first.second,l->first.first}, vec[i]));
}
// i번째점은 당연히 뒤에 확인할게 있음으로 후보 점이 된다.
m[{vec[i].second, vec[i].first}] = 0;
}
cout << ans << "\n";
return 0;
}
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------
#define MAX_N 101
vector<int> map[MAX_N];
int occupy[MAX_N];
int occupied[MAX_N];
bool visit[MAX_N];
bool dfs(int x) {
visit[x] = true;
for (int i = 0; i < map[x].size(); i++) {
int y = map[x][i];
if (occupied[y] == -1 || (!visit[occupied[y]] && dfs(occupied[y]))) {
occupy[x] = y;
occupied[y] = x;
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int N, M; cin >> N >> M;
for (int i = 0; i < M; i++) {
int a, b; cin >> a >> b;
map[a].push_back(b);
}
memset(occupy, -1, sizeof(occupy));
memset(occupied, -1, sizeof(occupied));
int ans = 0;
for (int i = 1; i <= N; i++) {
if (occupy[i] == -1) {
memset(visit, false, sizeof(visit));
if (dfs(i)) ans++;
}
}
cout << ans << endl;
}
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
//--------------------------------------------------------------------------------------
#define MAX_N 52
int c[MAX_N][MAX_N]; // 흐르는 양
int f[MAX_N][MAX_N]; // 흐르고 있는 양
int visit[MAX_N]; // 한번 que가 돌때마다 visit 이 -1로 초기화 된다.
vector<int> map[MAX_N];
// 애드몬드 카프 알고리즘
int maxFlow(int start, int end) {
int ret = 0;
while (1) {
memset(visit, -1, sizeof(visit)); // 모든 정점 방문 초기화
queue<int> q;
q.push(start); // start 점에서 end 점까지 흘려 보낸다.
while (!q.empty()) {
int front = q.front(); q.pop();
for (int i = 0; i < map[front].size(); i++) {
int e = map[front][i];
if (c[front][e] - f[front][e] > 0 && visit[e] == -1) {
// 흐를 수 있다 && 이번 BFS에서 흐른적이 없다.
q.push(e);
visit[e] = front; // front에서 e로 흘렀다는 것을 알려준다.
if (e == end) break; // end 점을 찾게되면 flow 중지
}
}
}
// 모든 경로를 찾은 경우
if (visit[end] == -1) break; // BFS에서 end 점을 방문하지 않았다 -> 더이상 흐르는 경우가 없다.
int flow = INT_MAX; // 최솟값을 찾기 위함
for (int i = end; i != start; i = visit[i]) {
flow = min(flow, c[visit[i]][i] - f[visit[i]][i]);
}
for (int i = end; i != start; i = visit[i]) {
// 음의 간선이 있다고 생각함으로써 모든 경우의 수를 탐색 할 수 있게 된다.
f[visit[i]][i] += flow;
f[i][visit[i]] -= flow;
}
ret += flow;
}
return ret;
}
int getID(char c) {
int ret;
if (c >= 97) {
ret = c - 97;
ret += 26;
}
else {
ret = c - 65;
}
return ret;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) {
char a, b; int w; cin >> a >> b >> w;
int A = getID(a);
int B = getID(b);
//cout << a << " : " << A << " " << b << " : "<< B << endl;
map[A].push_back(B);
map[B].push_back(A);
c[A][B] += w;
c[B][A] += w;
}
cout << maxFlow(0, 25) << "\n";
}
