結果
| 問題 |
No.119 旅行のツアーの問題
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:11:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 8,594 bytes |
| コンパイル時間 | 857 ms |
| コンパイル使用メモリ | 93,080 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:10 |
| 合計ジャッジ時間 | 1,865 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 19 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <limits>
#include <algorithm> // Required for std::min
using namespace std;
// Use long long for capacities and flow values to avoid potential overflow.
// The problem constraints N <= 40 and B_i, C_i <= 100 imply total weight <= 40 * (100+100) = 8000.
// Max flow value will be at most 8000. This fits within 32-bit integers, but using long long is safer.
typedef long long ll;
// Define a large value to represent infinity for edge capacities.
// It should be larger than the maximum possible flow value (sum of all B_i or C_i), which is at most 4000.
// A value like 10^10 is safe. Using 1e15 just to be extra cautious.
const ll INF = 1e15;
// Structure to represent an edge in the residual graph for max flow calculation.
struct Edge {
int to; // Target node index
ll capacity; // Residual capacity of the edge
int rev; // Index of the reverse edge in the adjacency list of the target node 'to'. Used to update residual capacity efficiently.
};
// Global variables for max flow computation:
vector<vector<Edge>> graph; // Adjacency list representation of the graph
vector<int> level; // Stores the level (distance from source) of each node in the level graph built by BFS.
vector<int> iter; // Stores the next edge index to explore in DFS for each node. Optimization for Dinic.
// Function to add a directed edge and its corresponding reverse edge to the graph.
// The reverse edge is necessary for the max flow algorithm to "push back" flow.
void add_edge(int from, int to, ll capacity) {
// Ensure capacity is non-negative. Although problem constraints say B_i, C_i >= 0, good practice.
if (capacity < 0) capacity = 0;
// Add forward edge
graph[from].push_back({to, capacity, (int)graph[to].size()});
// Add reverse edge with 0 initial capacity.
graph[to].push_back({from, 0, (int)graph[from].size() - 1});
}
// Breadth-First Search (BFS) to build the level graph.
// Returns true if the sink 't' is reachable from the source 's', false otherwise.
bool bfs(int s, int t) {
level.assign(graph.size(), -1); // Initialize all levels to -1 (unreachable)
queue<int> q;
level[s] = 0; // Source node is at level 0
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
// Explore neighbors
for (const auto& edge : graph[v]) {
// If edge has positive residual capacity and the target node hasn't been reached yet
if (edge.capacity > 0 && level[edge.to] < 0) {
level[edge.to] = level[v] + 1; // Set level of the target node
q.push(edge.to);
}
}
}
// Check if sink 't' was reached
return level[t] != -1;
}
// Depth-First Search (DFS) to find augmenting paths in the level graph.
// Pushes flow 'f' along the path found from node 'v' to sink 't'.
// Returns the amount of flow pushed.
ll dfs(int v, int t, ll f) {
if (v == t) return f; // Base case: reached the sink
// Use iterator 'iter' to avoid re-checking edges that yielded no flow previously from this node 'v'.
for (int& i = iter[v]; i < graph[v].size(); ++i) {
Edge& e = graph[v][i];
// Check if edge has positive capacity and leads to a node in the next level (strictly increasing level).
if (e.capacity > 0 && level[v] < level[e.to]) {
// Recursively call DFS for the target node 'e.to'.
// The flow 'f' passed down is limited by the minimum of remaining flow 'f' and edge capacity 'e.capacity'.
ll d = dfs(e.to, t, min(f, e.capacity));
if (d > 0) { // If flow was successfully pushed down this path
e.capacity -= d; // Decrease capacity of the forward edge
graph[e.to][e.rev].capacity += d; // Increase capacity of the reverse edge
return d; // Return the amount of flow pushed
}
}
}
// No augmenting path found from node 'v'
return 0;
}
// Dinic's algorithm to compute maximum flow from source 's' to sink 't'.
ll max_flow(int s, int t) {
ll total_flow = 0;
// Repeat as long as BFS finds a path from 's' to 't' (i.e., sink is reachable in residual graph)
while (bfs(s, t)) {
iter.assign(graph.size(), 0); // Reset DFS iterators for the new level graph
ll flow_increment;
// Keep finding augmenting paths using DFS in the current level graph until no more paths exist.
// Pass INF as initial flow capacity for DFS path finding.
while ((flow_increment = dfs(s, t, INF)) > 0) {
total_flow += flow_increment;
}
}
return total_flow; // Return the total maximum flow computed
}
int main() {
// Optimize input/output operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of countries
cin >> N;
vector<ll> B(N), C(N); // B_i: satisfaction for taking tour, C_i: satisfaction for not taking tour (if visited)
ll total_potential_satisfaction = 0;
for (int i = 0; i < N; ++i) {
cin >> B[i] >> C[i];
// Sum up all potential satisfaction values. This is the max possible value if there were no constraints.
// The reduction relates max weight independent set to min vertex cover using this total weight.
total_potential_satisfaction += B[i] + C[i];
}
int M; // Number of constraints
cin >> M;
vector<pair<int, int>> constraints(M);
for (int i = 0; i < M; ++i) {
// Read constraint pairs (D_j, E_j). D_j < E_j guaranteed.
cin >> constraints[i].first >> constraints[i].second;
}
// Setup the graph for max flow calculation.
// Total nodes = Source + Sink + 2 nodes per country (one for state 1, one for state 2).
int num_nodes = 2 * N + 2;
int S = 0; // Source node index
int T = 2 * N + 1; // Sink node index
graph.resize(num_nodes);
// Node mapping convention:
// Source node S: index 0
// Sink node T: index 2N+1
// Country i, choice "visit, no tour" (state 1, gain C_i): node i+1. These nodes form partition L.
// Country i, choice "visit, take tour" (state 2, gain B_i): node N+i+1. These nodes form partition R.
// Add edges based on the Minimum Weight Vertex Cover reduction for bipartite graphs.
// Edges from source S to nodes in partition L:
for (int i = 0; i < N; ++i) {
// Edge S -> I_{i,1} with capacity C_i. Represents the "cost" of NOT picking state 1 (which has profit C_i).
add_edge(S, i + 1, C[i]);
}
// Edges from nodes in partition R to sink T:
for (int i = 0; i < N; ++i) {
// Edge I_{i,2} -> T with capacity B_i. Represents the "cost" of NOT picking state 2 (which has profit B_i).
add_edge(N + i + 1, T, B[i]);
}
// Edges representing mutual exclusion within each country:
// Cannot pick both state 1 and state 2 for the same country i.
// This corresponds to an edge between I_{i,1} and I_{i,2} in the bipartite graph.
// For the flow network, add a directed edge from L node to R node.
for (int i = 0; i < N; ++i) {
// Edge I_{i,1} -> I_{i,2} with infinite capacity. Ensures if I_{i,1} is on S side and I_{i,2} on T side, cut is infinite.
add_edge(i + 1, N + i + 1, INF);
}
// Edges representing the problem constraints:
// Constraint (D_j, E_j): Forbids state combination (s_{D_j}=2, s_{E_j}=1).
// This means we cannot simultaneously select node I_{D_j, 2} (profit B_{D_j}) and node I_{E_j, 1} (profit C_{E_j}).
// This corresponds to an edge between I_{D_j, 2} (in R) and I_{E_j, 1} (in L).
// For the flow network, add a directed edge from the L node to the R node.
for (int i = 0; i < M; ++i) {
int Dj = constraints[i].first;
int Ej = constraints[i].second;
// Node for I_{E_j, 1} is Ej + 1 (L partition)
// Node for I_{D_j, 2} is N + Dj + 1 (R partition)
// Add edge I_{E_j, 1} -> I_{D_j, 2} with infinite capacity.
add_edge(Ej + 1, N + Dj + 1, INF);
}
// Calculate the minimum cut value using the max flow algorithm.
// Min cut value = Minimum Weight Vertex Cover value.
ll min_cut_value = max_flow(S, T);
// The maximum satisfaction corresponds to the Maximum Weight Independent Set value.
// Max Weight Independent Set = Total vertex weight - Min Weight Vertex Cover.
ll max_satisfaction = total_potential_satisfaction - min_cut_value;
cout << max_satisfaction << endl;
return 0;
}