layout: post title: 高项计算 subtitle: date: 2020-10-30 author: fsanren header-img: img/lyx-h-01.jpg catalog: true tags: - 软考 —
高项计算
-
线性规划求最值
给定类似: x + 2y <= 200 2x + 3y <= 400 4x + y <= 400 求 400x + 200y 最大值-
画图得出面积区间, 设最值为t = ax + by, 则得出函数 y = -a/bx + t/b, 画出切线得最大截距
-
简便法: 直接带入方程求出交点, 将交点带入t = ax + by
-
-
最小生成树
Kruskal’s algorithm initially places all the nodes of the original graph isolated from each other, to form a forest of single node trees, and then gradually merges these trees, combining at each iteration any two of all the trees with some edge of the original graph. Before the execution of the algorithm, all edges are sorted by weight (in non-decreasing order). Then begins the process of unification: pick all edges from the first to the last (in sorted order), and if the ends of the currently picked edge belong to different subtrees, these subtrees are combined, and the edge is added to the answer. After iterating through all the edges, all the vertices will belong to the same sub-tree, and we will get the answer.
The simplest implementation
struct Edge {
int u, v, weight;
bool operator<(Edge const& other) {
return weight < other.weight;
}
};
int n;
vector<Edge> edges;
int cost = 0;
vector<int> tree_id(n);
vector<Edge> result;
for (int i = 0; i < n; i++)
tree_id[i] = i;
sort(edges.begin(), edges.end());
for (Edge e : edges) {
if (tree_id[e.u] != tree_id[e.v]) {
cost += e.weight;
result.push_back(e);
int old_id = tree_id[e.u], new_id = tree_id[e.v];
for (int i = 0; i < n; i++) {
if (tree_id[i] == old_id)
tree_id[i] = new_id;
}
}
}
