2025-5-21 네트워크 유량 문제 풀이 노트
le0n님의 강의를 기반으로 정리한 네트워크 유량 문제 풀이 노트이다.
목차
- CF2046 D - For the Emperor!
- ICPC 2023 Polish E - Express Eviction
- ABC397 G - Maximize Distance
- ARC142 E - Pairing Wizards
- CF1427 G - One Billion Shades of Grey
- ICPC 2024 Shanghai K - Knights of Night
- AGC031 E - Snuke the Phantom Thief
- [Ynoi Easy Round 2018]星野瑠美衣
- KAIST 2019 J - Jealous Teachers
CF2046 D - For the Emperor!
이 문제는 강하게 연결된 구성요소를 먼저 축소한 후, 각 점을 입구와 출구로 분할한다. 입구에서 출구로의 유량은 메시지를运반하는 행위를 나타낸다. 그 다음 최소 비용 유량 알고리즘을 적용하면 된다.
const int MAXV = 205;
const int MAXE = 805;
const int BOUND = 1000;
const int INF = 1e9 + 7;
int vertexCount, edgeCount;
int initialValue[MAXV];
int componentValue[MAXV];
int firstEdge[MAXV], nextEdge[MAXE];
int toNode[MAXE], edgeIdx;
int discTime[MAXV], lowLink[MAXV], timer;
int stackNode[MAXV], inStack[MAXV], stackTop;
int componentCount, compId[MAXV];
int getNodeId(int vertex, int type) {
return vertex + type * componentCount;
}
void addDirectedEdge(int from, int to) {
nextEdge[++edgeIdx] = firstEdge[from];
toNode[edgeIdx] = to;
firstEdge[from] = edgeIdx;
}
void tarjanDFS(int current) {
discTime[current] = lowLink[current] = ++timer;
stackNode[++stackTop] = current;
inStack[current] = 1;
for(int edge = firstEdge[current]; edge; edge = nextEdge[edge]) {
int neighbor = toNode[edge];
if(!discTime[neighbor]) {
tarjanDFS(neighbor);
lowLink[current] = min(lowLink[current], lowLink[neighbor]);
} else if(inStack[neighbor]) {
lowLink[current] = min(lowLink[current], discTime[neighbor]);
}
}
if(discTime[current] == lowLink[current]) {
componentCount++;
while(true) {
int topNode = stackNode[stackTop--];
compId[topNode] = componentCount;
inStack[topNode] = 0;
if(topNode == current) break;
}
}
}
namespace MinCostFlow {
const int NODES = 605;
const int EDGES = 10005;
const int INFINITY = 0x3f3f3f3f;
struct EdgeInfo {
int capacity;
int cost;
int next;
int destination;
} edges[EDGES];
int head[NODES], edgeCnt;
int source, sink;
int dist[NODES], flow[NODES], parent[NODES];
bool inQueue[NODES];
void initialize() {
memset(head, 0, sizeof head);
edgeCnt = 1;
}
void addFlowEdge(int u, int v, int cap, int cost) {
edges[++edgeCnt] = {cap, cost, head[u], v};
head[u] = edgeCnt;
edges[++edgeCnt] = {0, -cost, head[v], u};
head[v] = edgeCnt;
}
bool shortestPath() {
fill(dist, dist + NODES, INFINITY);
fill(inQueue, inQueue + NODES, false);
queue<int> q;
dist[source] = 0;
flow[source] = INF;
inQueue[source] = true;
q.push(source);
while(!q.empty()) {
int u = q.front();
q.pop();
inQueue[u] = false;
for(int e = head[u]; e; e = edges[e].next) {
if(!edges[e].capacity) continue;
int v = edges[e].destination;
if(dist[v] > dist[u] + edges[e].cost) {
dist[v] = dist[u] + edges[e].cost;
flow[v] = min(flow[u], edges[e].capacity);
parent[v] = e;
if(!inQueue[v]) {
inQueue[v] = true;
q.push(v);
}
}
}
}
return dist[sink] != INFINITY;
}
pair<int,int> computeMinCost(int src, int dst) {
source = src;
sink = dst;
int totalFlow = 0;
int totalCost = 0;
while(shortestPath()) {
totalFlow += flow[sink];
totalCost += flow[sink] * dist[sink];
int u = sink;
while(u != source) {
int e = parent[u];
edges[e].capacity -= flow[sink];
edges[e ^ 1].capacity += flow[sink];
u = edges[e ^ 1].destination;
}
}
return {totalFlow, totalCost};
}
}
void solveProblem() {
cin >> vertexCount >> edgeCount;
for(int i = 1; i <= vertexCount; i++) cin >> initialValue[i];
edgeIdx = 0;
fill(firstEdge, firstEdge + vertexCount + 1, 0);
for(int i = 0; i < edgeCount; i++) {
int u, v;
cin >> u >> v;
addDirectedEdge(u, v);
}
timer = stackTop = componentCount = 0;
for(int i = 1; i <= vertexCount; i++) {
discTime[i] = lowLink[i] = inStack[i] = 0;
}
for(int i = 1; i <= vertexCount; i++) {
if(!discTime[i]) tarjanDFS(i);
}
for(int i = 1; i <= componentCount; i++) componentValue[i] = 0;
for(int i = 1; i <= vertexCount; i++) componentValue[compId[i]] += initialValue[i];
MinCostFlow::initialize();
int superSource = 0;
int superSink = componentCount * 3 + 1;
for(int i = 1; i <= componentCount; i++) {
if(componentValue[i]) {
MinCostFlow::addFlowEdge(superSource, getNodeId(i, 0), componentValue[i], 0);
MinCostFlow::addFlowEdge(getNodeId(i, 0), getNodeId(i, 1), 1, 1);
MinCostFlow::addFlowEdge(getNodeId(i, 0), getNodeId(i, 2), INF, 0);
}
MinCostFlow::addFlowEdge(getNodeId(i, 1), getNodeId(i, 2), 1, -BOUND);
MinCostFlow::addFlowEdge(getNodeId(i, 1), getNodeId(i, 2), INF, 0);
MinCostFlow::addFlowEdge(getNodeId(i, 2), superSink, INF, 0);
}
for(int u = 1; u <= vertexCount; u++) {
for(int e = firstEdge[u]; e; e = nextEdge[e]) {
int v = toNode[e];
if(compId[u] != compId[v]) {
MinCostFlow::addFlowEdge(getNodeId(compId[u], 2), getNodeId(compId[v], 1), INF, 0);
}
}
}
auto result = MinCostFlow::computeMinCost(superSource, superSink);
if(result.second >= -BOUND * (componentCount - 1)) {
cout << -1 << endl;
} else {
cout << BOUND + (result.second % BOUND) << endl;
}
}
ICPC 2023 Polish E - Express Eviction
원래 그래프의 이중 그래프를 고려하면, 경로가 있다는 것은 이중 그래프에서 왼쪽 하단에서 오른쪽 상단으로 연결되지 않음을 의미한다. 따라서 최소 컷 문제로 변환할 수 있다.
namespace MaxFlow {
const int MAXN = 5005;
const int MAXM = 1000005;
const int INFINITY = 0x3f3f3f3f;
struct FlowEdge {
int next;
int to;
int capacity;
} edges[MAXM];
int head[MAXN], edgeCnt;
int source, sink;
int level[MAXN], current[MAXN];
void initialize() {
edgeCnt = 1;
memset(head, 0, sizeof head);
}
void addEdge(int from, int to, int cap) {
edges[++edgeCnt] = {head[from], to, cap};
head[from] = edgeCnt;
edges[++edgeCnt] = {head[to], from, 0};
head[to] = edgeCnt;
}
bool bfs() {
fill(level, level + MAXN, INFINITY);
queue<int> q;
level[source] = 0;
q.push(source);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int e = head[u]; e; e = edges[e].next) {
if(!edges[e].capacity) continue;
int v = edges[e].to;
if(level[v] == INFINITY) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[sink] != INFINITY;
}
int sendFlow(int u, int flow) {
if(u == sink || !flow) return flow;
int result = 0;
for(int &e = current[u]; e; e = edges[e].next) {
if(!edges[e].capacity) continue;
int v = edges[e].to;
if(level[v] != level[u] + 1) continue;
int pushed = sendFlow(v, min(flow, edges[e].capacity));
if(!pushed) continue;
edges[e].capacity -= pushed;
edges[e ^ 1].capacity += pushed;
flow -= pushed;
result += pushed;
if(!flow) return result;
}
return result;
}
int dinic(int src, int dst) {
source = src;
sink = dst;
int totalFlow = 0;
while(bfs()) {
copy(head, head + MAXN, current);
totalFlow += sendFlow(source, INFINITY);
}
return totalFlow;
}
}
const int GRID_SIZE = 55;
const int LARGE_INF = 1e9 + 7;
int gridRows, gridCols;
string grid[GRID_SIZE];
int gridIndex(int x, int y, int layer) {
return (x - 1) * gridCols + y + layer * gridRows * gridCols;
}
void solveProblem() {
cin >> gridRows >> gridCols;
for(int i = 1; i <= gridRows; i++) {
cin >> grid[i];
grid[i] = " " + grid[i];
}
int sourceNode = 0;
int sinkNode = gridIndex(gridRows, gridCols, 1) + 1;
MaxFlow::initialize();
for(int i = 1; i <= gridRows; i++) {
for(int j = 1; j <= gridCols; j++) {
if(grid[i][j] == '#') {
MaxFlow::addEdge(gridIndex(i, j, 0), gridIndex(i, j, 1), 1);
if(j == 1 || i == gridRows) {
MaxFlow::addEdge(sourceNode, gridIndex(i, j, 0), LARGE_INF);
}
if(i == 1 || j == gridCols) {
MaxFlow::addEdge(gridIndex(i, j, 1), sinkNode, LARGE_INF);
}
for(int dx = -2; dx <= 2; dx++) {
for(int dy = -2; dy <= 2; dy++) {
int x = i + dx;
int y = j + dy;
if(x < 1 || x > gridRows || y < 1 || y > gridCols) continue;
if(grid[x][y] != '#') continue;
MaxFlow::addEdge(gridIndex(i, j, 1), gridIndex(x, y, 0), LARGE_INF);
}
}
}
}
}
cout << MaxFlow::dinic(sourceNode, sinkNode) << endl;
}
ABC397 G - Maximize Distance
최단 경로를 1로 만들고 싶다면 최소 컷 문제로 변환할 수 있다. 확장을 위해 각 정점을 여러 거리 정점으로 분할한다. 정점 u의 최단 경로가 d 이상인지를 (u,d) 노드로 표현한다. (u,d) → (v,d+1) 간선은 절단할 수 없고, (u,d) → (v,d) 간선을 절단하려면 1의 비용이 필요하다.
namespace DinicMaxFlow {
const int MAXN = 1005;
const int MAXM = 100005;
const int INFINITY = 0x3f3f3f3f;
struct Edge { int next, to, cap; } edges[MAXM];
int head[MAXN], edgeCnt;
int S, T, level[MAXN], it[MAXN];
void init() {
edgeCnt = 1;
memset(head, 0, sizeof head);
}
void addEdge(int u, int v, int w) {
edges[++edgeCnt] = {head[u], v, w};
head[u] = edgeCnt;
edges[++edgeCnt] = {head[v], u, 0};
head[v] = edgeCnt;
}
bool bfs() {
memset(level, -1, sizeof level);
queue<int> q;
level[S] = 0;
q.push(S);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int e = head[u]; e; e = edges[e].next) {
if(!edges[e].cap) continue;
int v = edges[e].to;
if(level[v] < 0) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[T] >= 0;
}
int dfs(int u, int f) {
if(u == T || !f) return f;
for(int &e = it[u]; e; e = edges[e].next) {
if(!edges[e].cap) continue;
int v = edges[e].to;
if(level[v] != level[u] + 1) continue;
int ret = dfs(v, min(f, edges[e].cap));
if(!ret) continue;
edges[e].cap -= ret;
edges[e ^ 1].cap += ret;
return ret;
}
return 0;
}
int maxFlow(int src, int dst) {
S = src;
T = dst;
int flow = 0;
while(bfs()) {
memcpy(it, head, sizeof it);
int f;
while((f = dfs(S, INFINITY)) > 0) flow += f;
}
return flow;
}
}
const int MAXM = 105;
const int LARGE_INF = 1e9 + 7;
int numVertices, edgeCount, limitK;
int edgeU[MAXM], edgeV[MAXM];
int nodeId(int x, int y) {
return x + y * numVertices;
}
void solveProblem() {
cin >> numVertices >> edgeCount >> limitK;
for(int i = 1; i <= edgeCount; i++) {
cin >> edgeU[i] >> edgeV[i];
}
DinicMaxFlow::init();
int S = nodeId(1, 0);
int T = nodeId(numVertices, numVertices);
for(int u = 1; u <= numVertices; u++) {
for(int i = 1; i <= numVertices; i++) {
DinicMaxFlow::addEdge(nodeId(u, i - 1), nodeId(u, i), LARGE_INF);
}
}
int currentFlow = 0;
for(int i = 1; i <= numVertices; i++) {
for(int j = 1; j <= edgeCount; j++) {
DinicMaxFlow::addEdge(nodeId(edgeU[j], i - 1), nodeId(edgeV[j], i - 1), 1);
}
currentFlow += DinicMaxFlow::maxFlow(S, T);
if(currentFlow > limitK) {
cout << i - 1 << endl;
return;
}
for(int j = 1; j <= edgeCount; j++) {
DinicMaxFlow::addEdge(nodeId(edgeU[j], i - 1), nodeId(edgeV[j], i), LARGE_INF);
}
}
}
ARC142 E - Pairing Wizards
먼저 a_x와 a_y를 min(b_x, b_y)로 업데이트한다. 그 다음 a_x와 a_y 중 하나가 max(b_x, b_y)보다 크면 된다. a_x < b_x라면 max(b_x, b_y)는 b_x이므로, 두 가지 선택지가 있다: a_x를 b_x로 높이거나, 모든 a_y를 b_x로 높이거나. 이는 최소 컷으로 해결할 수 있다.
namespace DinicFlow {
const int MAXN = 11005;
const int MAXM = 100005;
const int INFINITY = 0x3f3f3f3f;
struct Edge { int next, to, cap; } edges[MAXM];
int head[MAXN], edgeCnt;
int S, T, level[MAXN], now[MAXN];
void init() {
edgeCnt = 1;
memset(head, 0, sizeof head);
}
void addEdge(int u, int v, int w) {
edges[++edgeCnt] = {head[u], v, w};
head[u] = edgeCnt;
edges[++edgeCnt] = {head[v], u, 0};
head[v] = edgeCnt;
}
bool bfs() {
memset(level, -1, sizeof level);
queue<int> q;
level[S] = 0;
q.push(S);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int e = head[u]; e; e = edges[e].next) {
if(!edges[e].cap) continue;
int v = edges[e].to;
if(level[v] < 0) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[T] >= 0;
}
int dfs(int u, int f) {
if(u == T || !f) return f;
for(int &e = now[u]; e; e = edges[e].next) {
if(!edges[e].cap) continue;
int v = edges[e].to;
if(level[v] != level[u] + 1) continue;
int pushed = dfs(v, min(f, edges[e].cap));
if(!pushed) continue;
edges[e].cap -= pushed;
edges[e ^ 1].cap += pushed;
return pushed;
}
return 0;
}
int maxFlow(int src, int dst) {
S = src;
T = dst;
int flow = 0;
while(bfs()) {
memcpy(now, head, sizeof now);
int pushed;
while((pushed = dfs(S, INFINITY)) > 0) flow += pushed;
}
return flow;
}
}
const int MAXN = 105;
const int MAXM = 10005;
const int VALUE_MAX = 100;
const int LARGE_INF = 1e9 + 7;
int numWizards;
int originalA[MAXN];
int currentA[MAXN], limitB[MAXN];
int pairCount, pairU[MAXM], pairV[MAXM];
int nodeIndex(int x, int y) {
return x + y * numWizards;
}
void solveProblem() {
cin >> numWizards;
for(int i = 1; i <= numWizards; i++) {
cin >> originalA[i] >> limitB[i];
currentA[i] = originalA[i];
}
cin >> pairCount;
for(int i = 1; i <= pairCount; i++) {
cin >> pairU[i] >> pairV[i];
int minVal = min(limitB[pairU[i]], limitB[pairV[i]]);
currentA[pairU[i]] = max(currentA[pairU[i]], minVal);
currentA[pairV[i]] = max(currentA[pairV[i]], minVal);
}
int answer = 0;
for(int i = 1; i <= numWizards; i++) {
answer += currentA[i] - originalA[i];
}
DinicFlow::init();
int source = 0;
int sink = nodeIndex(numWizards, VALUE_MAX) + 1;
for(int i = 1; i <= numWizards; i++) {
for(int j = 2; j <= VALUE_MAX; j++) {
DinicFlow::addEdge(nodeIndex(i, j), nodeIndex(i, j - 1), LARGE_INF);
}
}
for(int i = 1; i <= numWizards; i++) {
for(int j = currentA[i] + 1; j <= VALUE_MAX; j++) {
DinicFlow::addEdge(nodeIndex(i, j), sink, 1);
}
}
for(int i = 1; i <= numWizards; i++) {
if(currentA[i] < limitB[i]) {
DinicFlow::addEdge(source, i, limitB[i] - currentA[i]);
for(int j = 1; j <= pairCount; j++) {
int u = pairU[j];
int v = pairV[j];
if(u == i) DinicFlow::addEdge(i, nodeIndex(v, limitB[i]), LARGE_INF);
if(v == i) DinicFlow::addEdge(i, nodeIndex(u, limitB[i]), LARGE_INF);
}
}
}
answer += DinicFlow::maxFlow(source, sink);
cout << answer << endl;
}
CF1427 G - One Billion Shades of Grey
절댓값을 Σ_k [a < k][b ≥ k]로 변환하면 유량 문제를 풀 수 있다. k를枚举하고 매번 역流即可.
const int GRID_MAX = 205;
const int MAX_EDGES = 1000005;
int gridSize, value[GRID_MAX][GRID_MAX];
struct GraphEdge {
int next;
int to;
int weight;
} edges[MAX_EDGES];
int head[GRID_MAX * GRID_MAX], edgeCnt = 1;
int nodeState[GRID_MAX * GRID_MAX], visited[GRID_MAX * GRID_MAX];
void addUndirectedEdge(int u, int v) {
edges[++edgeCnt] = {head[u], v, 0};
head[u] = edgeCnt;
edges[++edgeCnt] = {head[v], u, 0};
head[v] = edgeCnt;
}
int cellIndex(int x, int y) {
return (x - 1) * gridSize + y;
}
int pushFlow(int node, int direction) {
if(nodeState[node] == 2 && direction) return 1;
if(nodeState[node] == 1 && !direction) return 1;
visited[node] = 1;
for(int e = head[node]; e; e = edges[e].next) {
int neighbor = edges[e].to;
if(visited[neighbor]) continue;
if(direction && edges[e].weight == 1) continue;
if(!direction && edges[e].weight != -1) continue;
if(pushFlow(neighbor, direction)) {
edges[e].weight++;
edges[e ^ 1].weight--;
return 1;
}
}
return 0;
}
void solveProblem() {
cin >> gridSize;
for(int i = 1; i <= gridSize; i++) {
for(int j = 1; j <= gridSize; j++) {
cin >> value[i][j];
}
}
for(int i = 1; i <= gridSize; i++) {
for(int j = 1; j <= gridSize; j++) {
if(value[i][j] >= 0) {
if(i < gridSize && value[i + 1][j] >= 0) {
addUndirectedEdge(cellIndex(i, j), cellIndex(i + 1, j));
}
if(j < gridSize && value[i][j + 1] >= 0) {
addUndirectedEdge(cellIndex(i, j), cellIndex(i, j + 1));
}
}
}
}
vector<pair<int, int>> edgeList;
for(int i = 1; i <= gridSize; i++) {
for(int j = 1; j <= gridSize; j++) {
if(value[i][j] > 0) {
nodeState[cellIndex(i, j)] = 2;
edgeList.push_back({value[i][j], cellIndex(i, j)});
}
}
}
sort(edgeList.begin(), edgeList.end());
long long flow = 0;
long long answer = 0;
for(int i = 0; i < (int)edgeList.size() - 1; i++) {
int currentNode = edgeList[i].second;
memset(visited, 0, sizeof visited);
while(pushFlow(currentNode, 0)) {
flow--;
memset(visited, 0, sizeof visited);
}
nodeState[currentNode] = 1;
memset(visited, 0, sizeof visited);
for(int j = 0; j <= i; j++) {
int targetNode = edgeList[j].second;
while(pushFlow(targetNode, 1)) {
flow++;
memset(visited, 0, sizeof visited);
}
}
answer += 1LL * flow * (edgeList[i + 1].first - edgeList[i].first);
}
cout << answer << endl;
}
ICPC 2024 Shanghai K - Knights of Night
각 정점에서 가장 큰 k개의 간선만 유지하면 된다. 좌우两侧의 정점에서 선택한 간선의 교집합을 구한다. 각 간선은 최대 2k개의 간선을 금지시키므로, 상위 2k^2개의 간선만 유지하면 된다. 그 다음 이분 매칭을 수행한다.
namespace MinCostFlow {
const int MAXN = 200005;
const int MAXM = 1000005;
const int INFINITY = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3f;
struct Edge { int next, to, cap, cost; } edges[MAXM];
int head[MAXN], edgeCnt;
int nodeCount, source, sink;
long long dist[MAXN];
bool inQueue[MAXN];
int flow[MAXN], parentEdge[MAXN];
void initialize(int size) {
edgeCnt = 1;
nodeCount = size;
for(int i = 0; i <= size; i++) head[i] = 0;
}
void addEdge(int u, int v, int cap, int cost) {
edges[++edgeCnt] = {head[u], v, cap, cost};
head[u] = edgeCnt;
edges[++edgeCnt] = {head[v], u, 0, -cost};
head[v] = edgeCnt;
}
bool spfa() {
for(int i = 0; i <= nodeCount; i++) {
dist[i] = INFLL;
inQueue[i] = false;
}
queue<int> q;
q.push(source);
dist[source] = 0;
flow[source] = INFINITY;
inQueue[source] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
inQueue[u] = false;
for(int e = head[u]; e; e = edges[e].next) {
if(!edges[e].cap) continue;
int v = edges[e].to;
if(dist[v] > dist[u] + edges[e].cost) {
dist[v] = dist[u] + edges[e].cost;
flow[v] = min(flow[u], edges[e].cap);
parentEdge[v] = e;
if(!inQueue[v]) {
inQueue[v] = true;
q.push(v);
}
}
}
}
return dist[sink] != INFLL;
}
long long minCost(int src, int dst) {
source = src;
sink = dst;
if(!spfa()) return INFLL;
int u = sink;
while(u != source) {
int e = parentEdge[u];
edges[e].cap -= flow[sink];
edges[e ^ 1].cap += flow[sink];
u = edges[e ^ 1].to;
}
return dist[sink];
}
}
const int MAXN = 100005;
const int MOD = 998244353;
const long long INFLL = 0x3f3f3f3f3f3f3f3f;
int knightCount, relationCount, paramK;
int valueA[MAXN], valueB[MAXN], sortedId[MAXN], prevIdx[MAXN];
set<int> neighborSet[MAXN];
struct EdgeInfo {
int left, right, weight;
bool operator<(const EdgeInfo& other) const {
if(weight == other.weight) {
if(left == other.left) return right < other.right;
return left < other.left;
}
return weight < other.weight;
}
};
void solveProblem() {
cin >> knightCount >> relationCount >> paramK;
for(int i = 1; i <= knightCount; i++) cin >> valueA[i];
for(int i = 1; i <= knightCount; i++) cin >> valueB[i];
for(int i = 0; i < relationCount; i++) {
int u, v;
cin >> u >> v;
neighborSet[u].insert(v);
}
vector<EdgeInfo> leftEdges, rightEdges;
for(int i = 1; i <= knightCount; i++) sortedId[i] = i;
sort(sortedId + 1, sortedId + knightCount + 1, [](int x, int y) {
return valueB[x] < valueB[y];
});
for(int i = 2; i <= knightCount; i++) {
if(valueB[sortedId[i]] == valueB[sortedId[i - 1]]) {
prevIdx[i] = prevIdx[i - 1];
} else {
prevIdx[i] = i - 1;
}
}
for(int i = 1; i <= knightCount; i++) {
int L = 1, R = knightCount, pos = 0;
while(L <= R) {
int mid = (L + R) >> 1;
if(valueA[i] + valueB[sortedId[mid]] < MOD) {
pos = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
int cnt = 0;
for(int iter = 0; iter < knightCount && cnt < paramK; iter++) {
if(pos == 0) pos = knightCount;
if(!neighborSet[i].count(sortedId[pos])) {
leftEdges.push_back({i, sortedId[pos], (valueA[i] + valueB[sortedId[pos]]) % MOD});
cnt++;
pos--;
} else {
pos = prevIdx[pos];
}
}
}
sort(sortedId + 1, sortedId + knightCount + 1, [](int x, int y) {
return valueA[x] < valueA[y];
});
for(int i = 2; i <= knightCount; i++) {
if(valueA[sortedId[i]] == valueA[sortedId[i - 1]]) {
prevIdx[i] = prevIdx[i - 1];
} else {
prevIdx[i] = i - 1;
}
}
for(int i = 1; i <= knightCount; i++) {
int L = 1, R = knightCount, pos = 0;
while(L <= R) {
int mid = (L + R) >> 1;
if(valueB[i] + valueA[sortedId[mid]] < MOD) {
pos = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
int cnt = 0;
for(int iter = 0; iter < knightCount && cnt < paramK; iter++) {
if(pos == 0) pos = knightCount;
if(!neighborSet[sortedId[pos]].count(i)) {
rightEdges.push_back({sortedId[pos], i, (valueB[i] + valueA[sortedId[pos]]) % MOD});
cnt++;
pos--;
} else {
pos = prevIdx[pos];
}
}
}
sort(leftEdges.begin(), leftEdges.end());
reverse(leftEdges.begin(), leftEdges.end());
sort(rightEdges.begin(), rightEdges.end());
reverse(rightEdges.begin(), rightEdges.end());
vector<EdgeInfo> finalEdges;
int limit = paramK * paramK * 2;
int leftPtr = 0, rightPtr = 0;
while(leftPtr < (int)leftEdges.size() && rightPtr < (int)rightEdges.size()) {
if(leftEdges[leftPtr] < rightEdges[rightPtr]) {
rightPtr++;
continue;
}
if(rightEdges[rightPtr] < leftEdges[leftPtr]) {
leftPtr++;
continue;
}
finalEdges.push_back(leftEdges[leftPtr]);
leftPtr++;
rightPtr++;
if((int)finalEdges.size() == limit) break;
}
map<int, int> leftMap, rightMap;
int leftCount = 0, rightCount = 0;
for(const auto& e : finalEdges) {
if(!leftMap.count(e.left)) leftMap[e.left] = ++leftCount;
if(!rightMap.count(e.right)) rightMap[e.right] = ++rightCount;
}
MinCostFlow::initialize(leftCount + rightCount + 1);
int sourceNode = 0;
int sinkNode = leftCount + rightCount + 1;
for(int i = 1; i <= leftCount; i++) {
MinCostFlow::addEdge(sourceNode, i, 1, 0);
}
for(int i = 1; i <= rightCount; i++) {
MinCostFlow::addEdge(leftCount + i, sinkNode, 1, 0);
}
for(const auto& e : finalEdges) {
MinCostFlow::addEdge(leftMap[e.left], leftCount + rightMap[e.right], 1, -e.weight);
}
bool possible = true;
long long result = 0;
for(int i = 1; i <= paramK; i++) {
long long cost = MinCostFlow::minCost(sourceNode, sinkNode);
if(cost == INFLL) possible = false;
else result -= cost;
if(!possible) cout << -1 << " ";
else cout << result << " ";
}
cout << endl;
}
AGC031 E - Snuke the Phantom Thief
훔친 보석의 개수를枚举한 후 상하한 비용 유량을 적용한다.
const int MAXV = 205;
const int MAXE = 1005;
const int VALUE_MAX = 100;
const int INFINITY = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3f;
const long long LARGE_VAL = 2e15;
int numGems, numRestrictions;
int gemX[MAXV], gemY[MAXV];
long long gemValue[MAXV];
int lowerBoundX[MAXV][2], lowerBoundY[MAXV][2];
int upperBoundX[MAXV][2], upperBoundY[MAXV][2];
struct Edge {
int next;
int to;
int capacity;
long long cost;
} edges[MAXE];
int head[MAXV], edgeCnt;
int source, sink, isValid;
long long distArr[MAXV];
bool visited[MAXV];
int flowAmount[MAXV], parentEdge[MAXV];
void initialize() {
edgeCnt = 1;
isValid = 1;
memset(head, 0, sizeof head);
}
void addEdge(int u, int v, int cap, long long cost) {
edges[++edgeCnt] = {head[u], v, cap, cost};
head[u] = edgeCnt;
edges[++edgeCnt] = {head[v], u, 0, -cost};
head[v] = edgeCnt;
}
bool spfa() {
memset(distArr, 0x3f, sizeof distArr);
memset(visited, 0, sizeof visited);
queue<int> q;
q.push(source);
distArr[source] = 0;
visited[source] = true;
flowAmount[source] = INFINITY;
while(!q.empty()) {
int u = q.front();
q.pop();
visited[u] = false;
for(int e = head[u]; e; e = edges[e].next) {
if(!edges[e].capacity) continue;
int v = edges[e].to;
if(distArr[v] > distArr[u] + edges[e].cost) {
distArr[v] = distArr[u] + edges[e].cost;
flowAmount[v] = min(flowAmount[u], edges[e].capacity);
parentEdge[v] = e;
if(!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
return distArr[sink] != INFLL;
}
long long minCostFlow() {
long long result = 0;
while(spfa()) {
result += distArr[sink] * flowAmount[sink];
int u = sink;
while(u != source) {
int e = parentEdge[u];
edges[e].capacity -= flowAmount[sink];
edges[e ^ 1].capacity += flowAmount[sink];
u = edges[e ^ 1].to;
}
}
return result;
}
void addRangeEdge(int u, int v, int lower, int upper) {
if(lower > upper) isValid = 0;
addEdge(u, v, upper - lower, 0);
}
void solveProblem() {
cin >> numGems;
for(int i = 1; i <= numGems; i++) {
cin >> gemX[i] >> gemY[i] >> gemValue[i];
}
for(int i = 1; i <= VALUE_MAX; i++) {
for(int j = 0; j < 2; j++) {
lowerBoundX[i][j] = lowerBoundY[i][j] = INFINITY;
upperBoundX[i][j] = upperBoundY[i][j] = INFINITY;
}
}
cin >> numRestrictions;
for(int i = 0; i < numRestrictions; i++) {
char direction;
int index, val;
cin >> direction >> index >> val;
if(direction == 'L') lowerBoundX[index][0] = min(lowerBoundX[index][0], val);
if(direction == 'R') upperBoundX[index][1] = min(upperBoundX[index][1], val);
if(direction == 'D') lowerBoundY[index][0] = min(lowerBoundY[index][0], val);
if(direction == 'U') upperBoundY[index][1] = min(upperBoundY[index][1], val);
}
for(int i = VALUE_MAX - 1; i >= 1; i--) {
lowerBoundX[i][0] = min(lowerBoundX[i][0], lowerBoundX[i + 1][0]);
lowerBoundY[i][0] = min(lowerBoundY[i][0], lowerBoundY[i + 1][0]);
}
for(int i = 2; i <= VALUE_MAX; i++) {
upperBoundX[i][1] = min(upperBoundX[i][1], upperBoundX[i - 1][1]);
upperBoundY[i][1] = min(upperBoundY[i][1], upperBoundY[i - 1][1]);
}
long long answer = 0;
source = VALUE_MAX * 2 + 2;
sink = VALUE_MAX * 2 + 3;
for(int targetCount = 1; targetCount <= numGems; targetCount++) {
initialize();
for(int j = 0; j < VALUE_MAX; j++) {
addRangeEdge(j, j + 1, targetCount - lowerBoundX[j][0], upperBoundX[j + 1][1]);
}
for(int j = 0; j < VALUE_MAX; j++) {
addRangeEdge(j + VALUE_MAX + 2, j + VALUE_MAX + 1, targetCount - lowerBoundY[j][0], upperBoundY[j + 1][1]);
}
for(int j = 1; j <= numGems; j++) {
addEdge(gemX[j], gemY[j] + VALUE_MAX + 1, 1, -gemValue[j]);
}
for(int j = 0; j < VALUE_MAX * 2 + 2; j++) {
if(j > 0 && j <= VALUE_MAX) {
// source connections already added via addRangeEdge
}
}
addEdge(VALUE_MAX + 1, 0, INFINITY, LARGE_VAL);
if(!isValid) continue;
long long cost = minCostFlow();
bool saturated = false;
for(int e = head[source]; e; e = edges[e].next) {
if(edges[e].capacity) saturated = true;
}
for(int e = head[sink]; e; e = edges[e].next) {
if(edges[e ^ 1].capacity) saturated = true;
}
if(!isValid || saturated) continue;
answer = max(answer, LARGE_VAL * targetCount - cost);
}
cout << answer << endl;
}
[Ynoi Easy Round 2018] 星野瑠美衣
절댓값 문제이기 때문에, 모든 양수와 음수情况的组合을枚举하고 최대값을 취한다. 그러면 양쪽 점의 기여를 독립적으로 처리할 수 있고, 비용 유량으로 모델링할 수 있다. 만들어진 그래프는 이분 그래프이고, 한쪽은 11개의 점만 있으므로 시뮬레이션 비용 유량 알고리즘을 사용하고 삭제 가능한 힙으로 증강 경로를 유지한다.
const int MAXN = 100005;
const int INFINITY = 0x3f3f3f3f;
template <typename T>
struct RemovableHeap {
priority_queue<T> addQueue, delQueue;
RemovableHeap() {
addQueue.push({-INFINITY, 0});
}
void insert(T x) {
addQueue.push(x);
}
void remove(T x) {
delQueue.push(x);
}
void clean() {
while(!addQueue.empty() && !delQueue.empty() && addQueue.top() == delQueue.top()) {
addQueue.pop();
delQueue.pop();
}
}
T top() {
clean();
return addQueue.top();
}
};
int vertexCount, edgeCount;
struct Point {
int x, y;
} pointsA[MAXN], pointsB[MAXN];
int weightArr[MAXN], coeffArr[MAXN];
int f[MAXN][9], g[MAXN][9];
int leftMatch[MAXN], rightMatch[MAXN];
RemovableHeap<pair<int,int>> heapSet[11][11];
pair<int,int> edgeWeight[11][11];
int distArr[11];
bool vis[11];
int prevNode[11];
int source, sink;
void spfa() {
for(int i = 0; i < 11; i++) distArr[i] = -INFINITY;
for(int i = 0; i < 11; i++) vis[i] = false;
queue<int> q;
q.push(source);
distArr[source] = 0;
vis[source] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for(int v = 0; v < 11; v++) {
if(u == v) continue;
int w = edgeWeight[u][v].first;
if(distArr[v] < distArr[u] + w) {
distArr[v] = distArr[u] + w;
prevNode[v] = u;
if(!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
}
void solveProblem() {
cin >> vertexCount >> edgeCount;
for(int i = 1; i <= vertexCount; i++) cin >> pointsA[i].x >> pointsA[i].y;
for(int i = 1; i <= edgeCount; i++) cin >> pointsB[i].x >> pointsB[i].y >> weightArr[i];
for(int i = 1; i <= vertexCount; i++) {
int j = i % vertexCount + 1;
coeffArr[i] = abs(pointsA[i].x - pointsA[j].x) + abs(pointsA[i].y - pointsA[j].y);
vector<int> xTerms = {
abs(pointsA[i].x - pointsA[j].x),
pointsA[i].x + pointsA[j].x,
-pointsA[i].x - pointsA[j].x
};
vector<int> yTerms = {
abs(pointsA[i].y - pointsA[j].y),
pointsA[i].y + pointsA[j].y,
-pointsA[i].y - pointsA[j].y
};
for(int k = 0; k < 9; k++) {
f[i][k] = xTerms[k / 3] + yTerms[k % 3];
}
}
for(int i = 1; i <= edgeCount; i++) {
vector<int> xTerms = {0, -pointsB[i].x * 2, pointsB[i].x * 2};
vector<int> yTerms = {0, -pointsB[i].y * 2, pointsB[i].y * 2};
for(int k = 0; k < 9; k++) {
g[i][k] = xTerms[k / 3] + yTerms[k % 3];
}
}
source = 9;
sink = 10;
long long result = 0;
for(int i = 1; i <= vertexCount; i++) result += coeffArr[i];
for(int i = 1; i <= edgeCount; i++) {
for(int k = 0; k < 9; k++) {
heapSet[source][k].insert({g[i][k] + weightArr[i], i});
}
}
for(int i = 1; i <= vertexCount; i++) {
for(int k = 0; k < 9; k++) {
heapSet[k][sink].insert({f[i][k] - coeffArr[i], i + edgeCount});
}
}
for(int iter = 0; iter < vertexCount; iter++) {
for(int i = 0; i < 11; i++) {
for(int j = 0; j < 11; j++) {
edgeWeight[i][j] = heapSet[i][j].top();
}
}
spfa();
result += distArr[sink];
int u = sink;
while(u != source) {
int v = prevNode[u];
int idx = edgeWeight[v][u].second;
if(v == source) {
for(int k = 0; k < 9; k++) {
heapSet[source][k].remove({g[idx][k] + weightArr[idx], idx});
}
leftMatch[idx] = u;
for(int k = 0; k < 9; k++) {
if(k != leftMatch[idx]) {
heapSet[leftMatch[idx]][k].insert({g[idx][k] - g[idx][leftMatch[idx]], idx});
}
}
} else if(u == sink) {
idx -= edgeCount;
for(int k = 0; k < 9; k++) {
heapSet[k][sink].remove({f[idx][k] - coeffArr[idx], idx + edgeCount});
}
rightMatch[idx] = v;
for(int k = 0; k < 9; k++) {
if(k != rightMatch[idx]) {
heapSet[k][rightMatch[idx]].insert({f[idx][k] - f[idx][rightMatch[idx]], idx + edgeCount});
}
}
} else if(idx <= edgeCount) {
for(int k = 0; k < 9; k++) {
if(k != leftMatch[idx]) {
heapSet[leftMatch[idx]][k].remove({g[idx][k] - g[idx][leftMatch[idx]], idx});
}
}
leftMatch[idx] = u;
for(int k = 0; k < 9; k++) {
if(k != leftMatch[idx]) {
heapSet[leftMatch[idx]][k].insert({g[idx][k] - g[idx][leftMatch[idx]], idx});
}
}
} else {
idx -= edgeCount;
for(int k = 0; k < 9; k++) {
if(k != rightMatch[idx]) {
heapSet[k][rightMatch[idx]].remove({f[idx][k] - f[idx][rightMatch[idx]], idx + edgeCount});
}
}
rightMatch[idx] = v;
for(int k = 0; k < 9; k++) {
if(k != rightMatch[idx]) {
heapSet[k][rightMatch[idx]].insert({f[idx][k] - f[idx][rightMatch[idx]], idx + edgeCount});
}
}
}
u = v;
}
cout << result << " ";
}
cout << endl;
}
KAIST 2019 J - Jealous Teachers
이 문제는 다음 성질을 사용한다:
성질 1: 학생 집합 S와 인접한 선생님의 수는 항상 |S|보다 크다.
성질 2: 처음 n-1명의 학생과 처음 n-1명의 선생님 사이에 완벽한 매칭이 존재한다.
필요한 것은 한 학생이 자신이 매칭된 선생님과 다른 선생님에게 꽃을 보내는 것이고, 이것이 트리 형태를 형성한다.
const int MAXN = 200005;
const int MAXE = 1000005;
const int INFINITY = 0x3f3f3f3f;
int studentCount, relationCount;
int matchedTeacher[MAXN], teacherOfStudent[MAXN];
vector<int> studentAdj[MAXN], teacherAdj[MAXN];
struct FlowEdge {
int next;
int to;
int capacity;
} edges[MAXE];
int head[MAXN], edgeCnt;
int source, sink;
int levelArr[MAXN], currentEdge[MAXN];
set<int> availableSet[MAXN];
int fromNode[MAXN], toNode[MAXN];
map<pair<int,int>, int> answerMap;
int dpValue[MAXN];
void init() {
edgeCnt = 1;
memset(head, 0, sizeof head);
}
void addFlowEdge(int u, int v, int cap) {
edges[++edgeCnt] = {head[u], v, cap};
head[u] = edgeCnt;
edges[++edgeCnt] = {head[v], u, 0};
head[v] = edgeCnt;
}
bool bfs() {
memset(levelArr, 0x3f, sizeof levelArr);
queue<int> q;
levelArr[source] = 0;
q.push(source);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int e = head[u]; e; e = edges[e].next) {
if(!edges[e].capacity) continue;
int v = edges[e].to;
if(levelArr[v] == INFINITY) {
levelArr[v] = levelArr[u] + 1;
q.push(v);
}
}
}
return levelArr[sink] != INFINITY;
}
int sendFlow(int u, int flow) {
if(u == sink || !flow) return flow;
int result = 0;
for(int &e = currentEdge[u]; e; e = edges[e].next) {
if(!edges[e].capacity) continue;
int v = edges[e].to;
if(levelArr[v] != levelArr[u] + 1) continue;
int pushed = sendFlow(v, min(flow, edges[e].capacity));
if(!pushed) continue;
edges[e].capacity -= pushed;
edges[e ^ 1].capacity += pushed;
flow -= pushed;
result += pushed;
if(!flow) return result;
}
return result;
}
int maxFlow(int src, int dst) {
source = src;
sink = dst;
int result = 0;
while(bfs()) {
memcpy(currentEdge, head, sizeof head);
result += sendFlow(src, INFINITY);
}
return result;
}
void dfsTree(int u) {
int remain = studentCount - 1;
for(int v : teacherAdj[u]) {
dfsTree(v);
remain -= dpValue[v];
answerMap[{teacherOfStudent[v], u}] = dpValue[v];
}
answerMap[{teacherOfStudent[u], u}] = remain;
dpValue[u] = studentCount - remain;
}
void solveProblem() {
cin >> studentCount >> relationCount;
init();
int sourceNode = 0;
int sinkNode = studentCount * 2;
for(int i = 1; i <= studentCount - 1; i++) {
addFlowEdge(sourceNode, i, 1);
}
for(int i = 1; i <= studentCount - 1; i++) {
addFlowEdge(i + studentCount - 1, sinkNode, 1);
}
for(int i = 0; i < relationCount; i++) {
int u, v;
cin >> u >> v;
fromNode[i] = u;
toNode[i] = v;
studentAdj[u].push_back(v);
if(u < studentCount && v < studentCount) {
addFlowEdge(u, v + studentCount - 1, 1);
}
}
if(maxFlow(sourceNode, sinkNode) != studentCount - 1) {
cout << -1 << endl;
return;
}
for(int u = 1; u <= studentCount - 1; u++) {
for(int e = head[u]; e; e = edges[e].next) {
if(edges[e ^ 1].capacity) {
int v = edges[e].to;
if(v == sourceNode) continue;
matchedTeacher[u] = v - studentCount + 1;
break;
}
}
}
for(int i = 1; i <= studentCount - 1; i++) {
teacherOfStudent[matchedTeacher[i]] = i;
}
for(int u = 1; u <= studentCount - 1; u++) {
for(int v : studentAdj[u]) {
if(v != matchedTeacher[u]) {
availableSet[v].insert(u);
}
}
}
queue<int> q;
q.push(studentCount);
for(int iter = 0; iter < studentCount - 1; iter++) {
int pos = -1;
while(!q.empty()) {
int u = q.front();
if(availableSet[u].empty()) {
q.pop();
continue;
}
pos = *availableSet[u].begin();
for(int v : studentAdj[pos]) {
if(v != matchedTeacher[pos]) {
availableSet[v].erase(pos);
}
}
break;
}
if(pos == -1) {
cout << -1 << endl;
return;
}
teacherAdj[q.front()].push_back(matchedTeacher[pos]);
q.push(matchedTeacher[pos]);
}
dfsTree(studentCount);
for(int i = 0; i < relationCount; i++) {
cout << answerMap[{fromNode[i], toNode[i]}] << endl;
}
}