QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181975 | #6414. Classical Maximization Problem | alexzhanUS | TL | 0ms | 0kb | C++17 | 4.1kb | 2023-09-17 06:58:58 | 2023-09-17 06:58:58 |
answer
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
class Neighbor {
public:
long long vertex;
int edgeIndex;
bool isTreeEdge = false;
Neighbor(long long axisValue, int edgeIndex): vertex(axisValue), edgeIndex(edgeIndex) {}
};
void buildDfsTree(map<long long, vector<Neighbor>>& adjacencyMatrix, set<long long>& visited, long long node, int& time, map<long long, int>& nodeToEntryTime) {
// *NOTE: the edge from a node to its parent is marked as a back edge.
time++;
nodeToEntryTime[node] = time;
visited.insert(node);
for (Neighbor& neighbor : adjacencyMatrix[node]) {
if (visited.find(neighbor.vertex) == visited.end()) { // not visited before
neighbor.isTreeEdge = true;
buildDfsTree(adjacencyMatrix, visited, neighbor.vertex, time, nodeToEntryTime);
}
// if it is already visited, it is a back edge, so you don't really need to do anything
}
}
bool pairEdges(map<long long, vector<Neighbor>>& adjacencyMatrix, vector<pair<int, int>>& pairs, long long node, long long parent, map<long long, int>& nodeToEntryTime) {
// return true if you used the edge from the node to its parent.
// return false otherwise.
set<int> notUsedEdges;
int parentEdgeIndex = 0;
for (Neighbor& neighbor : adjacencyMatrix[node]) {
if (neighbor.isTreeEdge) { // it is a spanning edge
if (!pairEdges(adjacencyMatrix, pairs, neighbor.vertex, node, nodeToEntryTime)) { // if neighbor is not used
notUsedEdges.insert(neighbor.edgeIndex);
}
} else { // it is a back edge.
if (nodeToEntryTime[neighbor.vertex] > nodeToEntryTime[node]) {
//TODO: add a check to make sure that this back edge is connecting node to something in its subtree
// rather than going upwards
notUsedEdges.insert(neighbor.edgeIndex);
} else if (neighbor.vertex == parent) {
parentEdgeIndex = neighbor.edgeIndex;
}
}
}
auto iterator = notUsedEdges.begin();
auto iterator2 = ++notUsedEdges.begin();
while (iterator != notUsedEdges.end() && iterator2 != notUsedEdges.end()) {
pairs.emplace_back(*iterator, *iterator2);
++++iterator;
++++iterator2;
}
if (notUsedEdges.size() == 1 && parentEdgeIndex != 0) {
pairs.emplace_back(parentEdgeIndex, *notUsedEdges.begin());
return true;
} else {
return false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int numOfTestCases;
cin >> numOfTestCases;
for (int i = 0; i < numOfTestCases; i++) {
int n;
cin >> n;
map<long long, vector<Neighbor>> adjacencyMatrix;
set<long long> allNodes;
for (int j = 0; j < (2 * n); j++) {
long long x, y;
cin >> x >> y;
y += 2e9 + 1;
adjacencyMatrix[x].emplace_back(y, j + 1);
adjacencyMatrix[y].emplace_back(x, j + 1);
allNodes.insert(x);
allNodes.insert(y);
}
set<long long> visited;
vector<pair<int, int>> pairs;
map<long long, int> nodeToEntryTime;
int time = 0;
for (auto& node : allNodes) {
if (visited.find(node) == visited.end()) {
buildDfsTree(adjacencyMatrix, visited, node, time, nodeToEntryTime);
pairEdges(adjacencyMatrix, pairs, node, -1e9 - 1, nodeToEntryTime);
}
}
cout << pairs.size() << "\n";
vector<bool> usedPoints(2 * n + 1);
for (auto& pair : pairs) {
cout << pair.first << " " << pair.second << "\n";
usedPoints[pair.first] = true;
usedPoints[pair.second] = true;
}
vector<int> notUsedPoints;
for (int j = 1; j <= 2 * n; j++) {
if (!usedPoints[j]) {
notUsedPoints.push_back(j);
}
}
for (int index = 0; index < notUsedPoints.size(); index += 2) {
cout << notUsedPoints[index] << " " << notUsedPoints[index + 1] << "\n";
}
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 2 0 0 0 1 1 0 1 1 2 0 0 0 1 0 2 0 3 2 0 0 1 1 2 2 3 3