myCPP
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
CCW, 선분 교차 판별
ll ccw(pll a, pll b, pll c) {
ll ret = (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
if (ret > 0) return 1;
else if (ret == 0) return 0;
else return -1;
}
bool isIntersect(pll a, pll b, pll c, pll d) {
ll ab = ccw(a, b, c) * ccw(a, b, d);
ll cd = ccw(c, d, a) * ccw(c, d, b);
if (ab == 0 && cd == 0) { // 서로 평행하거나, 평행하진 않지만 끝점만 만남
if (a > b) swap(a, b);
if (c > d) swap(c, d);
if (c <= b && a <= d) return true; // 서로 겹치거나, 끝점만 만남
else return false;
}
else { // 평행하지 않으면서 교차
if (ab <= 0 && cd <= 0) return true; // 서로 교차하거나, 선분 위에 한 점만 만나거나
else return false;
}
}
구간 합 Lazy propagation
const int SIZE = 1 << 21; // SIZE == 1 << (ceil(log2(N)) + 1)
ll arr[1000001];
ll seg[SIZE];
ll lazy[SIZE];
// start, end는 표적 대상의 범위
// nodeLeft, nodeRight는 0, N - 1으로 시작하여 범위를 줄여나감 (0 based)
ll init(int node, int start, int end) {
if (start == end) return seg[node] = arr[start];
int mid = (start + end) >> 1;
return seg[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end);
}
void update_lazy(int node, int nodeLeft, int nodeRight) {
if (lazy[node] != 0) {
// 만약 해당 세그먼트 트리 노드에 lazy 값이 있다면
if (nodeLeft != nodeRight) {
// 만약 리프노드가 아니라면 lazy 값을 자식노드에게 전파
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
seg[node] += lazy[node] * (nodeRight - nodeLeft + 1);
lazy[node] = 0; // 자식에게 전파 후, 자신 lazy 값은 삭제
}
else return;
}
void update_range(int node, int start, int end, int nodeLeft, int nodeRight, ll k) {
update_lazy(node, nodeLeft, nodeRight); // 항상 먼저 lazy 갱신
if (nodeLeft > end || nodeRight < start) return;
if (start <= nodeLeft && nodeRight <= end) {
lazy[node] += k;
update_lazy(node, nodeLeft, nodeRight);
return;
}
int mid = (nodeLeft + nodeRight) >> 1;
update_range(node * 2, start, end, nodeLeft, mid, k);
update_range(node * 2 + 1, start, end, mid + 1, nodeRight, k);
seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
ll sum_range(int node, int start, int end, int nodeLeft, int nodeRight) {
update_lazy(node, nodeLeft, nodeRight); // 항상 먼저 lazy 갱신
if (nodeLeft > end || nodeRight < start) return 0;
if (start <= nodeLeft && nodeRight <= end) return seg[node];
int mid = (nodeLeft + nodeRight) >> 1;
return sum_range(node * 2, start, end, nodeLeft, mid) + sum_range(node * 2 + 1, start, end, mid + 1, nodeRight);
}
유니온 파인드
int find(int x) {
if (p[x] < 0) return x;
return p[x] = find(p[x]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
p[a] += p[b];
p[b] = a;
}
큰 수 나머지
int getMod(string s, int d) {
int ret = 0;
for (int i = 0; i < s.size(); i++) {
ret *= 10;
ret += s[i] - '0';
ret %= d;
}
return ret;
}
다익스트라 // O(E log V)
vector<pii> adj[1001];
int dist[1001];
int dijkstra(int start, int end) {
for (int i = 0; i < 1001; i++) dist[i] = INF;
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int cur_dist = pq.top().X;
int cur_node = pq.top().Y;
pq.pop();
if (dist[cur_node] < cur_dist) continue;
for (pii next : adj[cur_node]) {
int next_node = next.X;
int next_dist = dist[cur_node] + next.Y;
if (next_dist >= dist[next_node]) continue;
dist[next_node] = next_dist;
pq.push({next_dist, next_node});
}
}
return dist[end];
}
벨만 포드 // O(VE)
vector<pii> adj[51];
ll dist[51];
bool minusCycle;
void bellmanFord(int start, int n) {
for (int i = 0; i < 51; i++) dist[i] = INF;
minusCycle = false;
dist[start] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (auto next : adj[j]) {
int nextNode = next.X;
ll nextDist = dist[j] + next.Y;
if (dist[j] == INF || dist[nextNode] <= nextDist) continue;
dist[nextNode] = nextDist;
if (i == n - 1) minusCycle = true;
}
}
}
}
compare 구조체 정의
struct A {
int node;
int cost;
};
struct compare {
bool operator()(A& a, A& b) {
return a.cost > b.cost; // cost 값을 기준으로 최소 힙
}
};
struct compare {
bool operator()(A& a, A& b) {
return a.cost < b.cost; // cost 값을 기준으로 최대 힙
}
};
최대 유량 (에드몬드-카프)
int c[305][305];
int f[305][305];
int prevv[305];
vector<int> adj[305];
int maximumFlow(int S, int E) {
int total = 0;
int source = S;
int sink = E;
while (1) {
for (int i = 0; i < 305; i++) prevv[i] = -1;
queue<int> que;
que.push(source);
while (!que.empty() && prevv[sink] == -1) {
int node = que.front();
que.pop();
if (node == sink) break;
for (int next : adj[node]) {
if (c[node][next] == f[node][next] || prevv[next] != -1) continue;
que.push(next);
prevv[next] = node;
}
}
if (prevv[sink] == -1) break; // 싱크로 향하는 증가 경로가 더 이상 없다면 while문 탈출
int flow = inf;
for (int i = sink; i != source; i = prevv[i]) flow = min(flow, c[prevv[i]][i] - f[prevv[i]][i]);
for (int i = sink; i != source; i = prevv[i]) {
f[prevv[i]][i] += flow;
f[i][prevv[i]] -= flow;
}
total += flow;
}
return total;
}
댓글