这是一道典型的最小生成树的题目， 利用Kruskal算法，先按照road的长度排序，若当前的road未在连接好的“城市组”里，则连通它。直到所有的城市全部连通，即所铺路径最短。 // runtime: 6ms // space: 488K #include <iostream> #include <algorithm> using namespace std; struct Road { int from; int to; int distance; bool operator< (const Road& r) const { return distanc...

并查集的题目 // runtime: 4ms // space: 608K #include <iostream> using namespace std; const int MAX = 10000; int father[MAX]; int height[MAX]; int inDegree[MAX]; bool visited[MAX]; void Initial () { // 初始化 for (int i = 0; i < MAX; ++i) { father[i] = i; height[i] = 0; visited[i] = false; inDegree[i...

背包问题变形

代码和0-1背包非常之像，只是由原来的容量固定，求最大价值，最小邮票数是每个邮票的价值(权重)一样，都为1(枚)，在背包大小固定的情况，求最少的邮票数。 // runtime: 4ms // space: 496K #include <iostream> #include <algorithm> using namespace std; const int MAX = 100000; int main() { int total, n; while (cin>> total >> n) { int stamp[n + 1]; int dp[n +...

dp

休息一天，在家看《雍正王朝》😂

背包问题