A [USACO3.1]最短网络 Agri-Net

题目背景

Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

题目描述

FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 \(10^5\)。

输入格式

第一行农场的个数 \(N\)（\(3 \leq N \leq 100\)）。

接下来是一个 \(N \times N\) 的矩阵，表示每个农场之间的距离。理论上，他们是 \(N\) 行，每行由 \(N\) 个用空格分隔的数组成，实际上，由于每行 \(80\) 个字符的限制，因此，某些行会紧接着另一些行。当然，对角线将会是 \(0\)，因为不会有线路从第 \(i\) 个农场到它本身。

输出格式

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

解题思路

纯最小生成树模板题，数据范围小，使用 prim 或 kruscal 都可

Kruscal

#include<bits/stdc++.h>
#define IOFAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 105;
struct node {
    int u, v, e;
};
int fa[maxn], n;
vector<node> edge;
bool cmp(const node& a, const node& b) {
    return a.e < b.e;
}
int find(int x) {
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void cob(int a, int b) {
    fa[find(a)] = find(b);
}
int main()
{
    IOFAST
    ll sum = 0;
    int e, cnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++) fa[i] = i;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) {
            cin >> e;
            if(i != j && i > j) edge.push_back({i, j, e});
        }
    sort(edge.begin(), edge.end(), cmp);
    for (int i = 0; i < edge.size() && cnt < n - 1; i++) {
        if(find(edge[i].u) != find(edge[i].v)) {
            cob(edge[i].u, edge[i].v);
            sum += edge[i].e;
            cnt++;
        }
    }
    cout << sum;
    return 0;
}

Prim

#include<bits/stdc++.h>
#define IOFAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 105;
int cost[maxn][maxn], dis[maxn], vis[maxn], n;
ll sum = 0;
ll prim() {
	ll sum = 0;
    memset(dis, inf, sizeof(dis));
	dis[0] = 0;
	for(int i = 0; i < n; i++) {
		int minc = inf, p = -1;
		for(int j = 0; j < n; j++) {
			if(!vis[j] && (p == -1 || dis[j] < dis[p])) {
				minc = dis[j];
				p = j;
			}
		}
        if(p == -1) return -1L;
		vis[p] = 1;
        sum += dis[p];
		for(int j = 0; j < n; j++) {
            if(!vis[j] && cost[p][j] != inf && cost[p][j] < dis[j]) {
                dis[j] = cost[p][j];
            }
        }
	}
    return sum;
}
int main()
{
    IOFAST
    int e, cnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) {
            cin >> e;
            if(i != j && i > j) cost[i][j] = cost[j][i] = e;
        }
    prim();
    cout << sum;
    return 0;
}

B 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 \(N,M\)，表示该图共有 \(N\) 个结点和 \(M\) 条无向边。

接下来 \(M\) 行每行包含三个整数 \(X_i,Y_i,Z_i\)，表示有一条长度为 \(Z_i\) 的无向边连接结点 \(X_i,Y_i\)。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

提示

数据规模：

对于 \(20\%\) 的数据，\(N\le 5\)，\(M\le 20\)。

对于 \(40\%\) 的数据，\(N\le 50\)，\(M\le 2500\)。

对于 \(70\%\) 的数据，\(N\le 500\)，\(M\le 10^4\)。

对于 \(100\%\) 的数据：\(1\le N\le 5000\)，\(1\le M\le 2\times 10^5\)，\(1\le Z_i \le 10^4\)。

解题思路

本题也是模板题，但数据范围较大，\(1\le N\le 5000\)，\(1\le M\le 2\times 10^5\)，\(1\le Z_i \le 10^4\)。
求长度之和 \(sum\) 记得开 long long

hint 1 如果遇到WA/RE/TLE，先检查是不是空间开小了以及出现非连通图的特判，输出orz

hint 2 如果仍旧WA，建议参考最新的讨论区，处理输入出现重边的情况（

如果您还未解决，联系我 : ）

以下为 prim 堆优化的 AC 代码

#include<bits/stdc++.h>
#define IOFAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
const int maxn = 5005, mx = 2e5 + 5;
int head[maxn], to[mx<<1], nxt[mx<<1], w[mx<<1], idx;
int vis[maxn], n;
ll sum = 0;
void add(int u, int v, int e) {
    to[idx] = v, w[idx] = e;
    nxt[idx] = head[u];
    head[u] = idx++;h
}
void prim() {
    int cnt = 0;
    priority_queue<pp, vector<pp>, greater<pp>> q;
    q.push({0, 1});
    while(!q.empty()) {
        pp e = q.top();
        q.pop();
        int u = e.second, d = e.first;
        if(vis[u]) continue;
        vis[u] = 1, sum += d, cnt++;
        for(int i = head[u]; i != -1; i = nxt[i]) {
            if(!vis[to[i]]) {
                q.push({w[i], to[i]});
            }
        }
    }
    if(cnt != n) cout << "orz";  
        else cout << sum;
}
int main()
{
    // IOFAST
    memset(head, -1, sizeof(head));
    int m, a, b, c;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    prim();
    return 0;
}

C 村村通

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

输入格式

输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 \(n\) 和道路数目 \(m\) ；随后的 \(m\) 行对应 \(m\) 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 \(1\) 到 \(n\) 编号。

注意：两个城市间可以有多条道路相通。

输出格式

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

提示

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1 \le n < 1000\) 。

解题思路

本题是最小生成树的小改动题，但难度没有加大。题目要求在已经修了部分路的情况下，求还需要修多少条路才能实现最小生成树。

最小生成树的边为顶点数 - 1，对于每一组输入的数据，我们跑一遍 kruscal 判断已修了的有效边数 \(cnt\)，输出结果为 \(n-1-cnt\)

AC code

#include<bits/stdc++.h>
#define IOFAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1005;
int fa[maxn], n, cnt;
int find(int x) {
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void cob(int a, int b) {
    fa[find(a)] = find(b);
}
void init() {
    for(int i = 1; i <= n; i++) fa[i] = i;
    cnt = 0;
}
int main()
{
    // IOFAST
    int m, u, v;
    while(cin >> n) {
        if(!n) break;
        init();
        cin >> m;
        for(int i = 0; i < m; i++) {
            cin >> u >> v;
            if(find(u) != find(v)) {
                cnt++;
                cob(u, v);
            }
        }
        cout << n - cnt - 1 << '\n';
    }
    return 0;
}

D [HNOI2006]公路修建问题

题目描述

OI island 是一个非常漂亮的岛屿，自开发以来，到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIER Association 组织成立了，旨在建立 OI island 的交通系统。

OI island 有 \(n\) 个旅游景点，不妨将它们从 \(1\) 到 \(n\) 标号。现在，OIER Association 需要修公路将这些景点连接起来。一条公路连接两个景点。公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花费要大一些。

OIER Association 打算修 \(n-1\) 条公路将这些景点连接起来（使得任意两个景点之间都会有一条路径）。为了保证公路系统的效率， OIER Association 希望在这 \(n-1\) 条公路之中，至少有 \(k\) 条 \((0 \le k \le n-1)\) 一级公路。OIER Association 也不希望为一条公路花费的钱。所以，他们希望在满足上述条件的情况下，花费最多的一条公路的花费尽可能的少。

而你的任务就是，在给定一些可能修建的公路的情况下，选择 \(n-1\) 条公路，满足上面的条件。

输入格式

文件第一行有三个数 \(n(1 \le n \le 10000)\)，\(k(0 \le k \le n-1),m(n-1 \le m \le 20000)\)，这些数之间用空格分开。\(N\) 和 \(k\) 如前所述，\(m\) 表示有 \(m\) 对景点之间可以修公路。

以下的 \(m-1\) 行，每一行有 \(4\) 个正整数 \(a,b,c_1,c_2\)，（\(1 \le a,b \le n,a \ne b,1 \le c_2 \le c_1 \le 30000\)），表示在景点 \(a\) 与 \(b\) 之间可以修公路，如果修一级公路，则需要 \(c_1\) 的花费，如果修二级公路，则需要 \(c_2\) 的花费。

在实际评测时，将只会有 \(m-1\) 行公路

输出格式

输出第一行有一个数据，表示花费最大的公路的花费。

接下来的 \(n-1\) 行，每行有两个正整数 \(t\) 和 \(p\)，\(t\) 和 \(p\) 表示在输入的第 \(t\) 对（按照输入的顺序，从 \(1\) 开始标号）景点之间修建 \(p\) 级公路。

\(n-1\) 条公路的输出必选 \(t\) 的大小递增，如果有多个方案使花费最大的公路花费最小，那么输出任意一个都可以。

解题思路

本题有两个标尺，即一级公路和二级公路的成本，并且指定了至少要有\(k\)条一级公路，要求花费最大公路成本最小。看似复杂，但实际上题目给的条件一级公路的建造费用一定大于二级公路，在此条件下，题目就非常简单了，所以我们只要优先选择完\(k\)条一级公路，然后再选择二级公路即可。
hint： 要求按输入顺序的升序输出，所以需要对输出的答案进行排序

#include<bits/stdc++.h>
#define IOFAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
const int maxn = 20005;
struct node {
    int u, v, c1, c2, idx;
};
vector<node> edge;
vector<pp> ans;
int fa[maxn>>1], n, k, m;
int find(int x) {
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void cob(int a, int b) {
    fa[find(a)] = find(b);
}
void init() {
    for(int i = 1; i <= n; i++) fa[i] = i;
}
bool cmp1(const node& a, const node& b) {
    return a.c1 == b.c1 ? a.c2 > b.c2 : a.c1 < b.c1;
}
bool cmp2(const node& a, const node& b) {
    return a.c2 < b.c2;
}
int main()
{
    IOFAST
    int mx = 0;
    node e;
    cin >> n >> k >> m;
    init();
    for(int i = 0; i < m - 1; i++) {
        cin >> e.u >> e.v >> e.c1 >> e.c2;
        e.idx = i + 1;
        edge.push_back(e);
    }
    sort(edge.begin(), edge.end(), cmp1);
    // 优先选择 k 条一级公路
    for(int i = 0; i < m - 1; i++) {
        if(ans.size() == k) break;
        if(find(edge[i].u) != find(edge[i].v)) {
            cob(edge[i].u, edge[i].v);
            mx = max(mx, edge[i].c1);
            ans.push_back({edge[i].idx, 1});
        }
    }
    sort(edge.begin(), edge.end(), cmp2);
    for(int i = 0; i < m - 1 && ans.size() < n; i++) {
        if(find(edge[i].u) != find(edge[i].v)) {
            cob(edge[i].u, edge[i].v);
            mx = max(mx, edge[i].c2);
            ans.push_back({edge[i].idx, 2});
        }
    }
    cout << mx << '\n';
    // 输出按 idx 升序，pair 的默认排序即可
    sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    }
    return 0;
}

E [APIO2008] 免费道路

题目描述

新亚（New Asia）王国有 N 个村庄，由 M 条道路连接。其中一些道路是鹅卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。

国王已决定保持尽可能少的道路免费，但是两个不同的村庄之间都应该一条且仅由一条 且仅由一条免费道路的路径连接。同时，虽然水泥路更适合现代交通的需要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好 K 条鹅卵石路免费。

举例来说，假定新亚王国的村庄和道路如图 3(a)所示。如果国王希望保持两条鹅卵石路免费，那么可以如图 3(b)中那样保持道路(1, 2)、(2, 3)、(3, 4)和(3, 5) 免费。该方案满足了国王的要求，因为：(1)两个村庄之间都有一条由免费道路组成的路径；(2)免费的道路已尽可能少；(3)方案中刚好有两条鹅卵石道路 (2, 3)和(3, 4)

图 3: (a)新亚王国中村庄和道路的一个示例。实线标注的是水泥路，虚线标注 的是鹅卵石路。(b)一个保持两条鹅卵石路免费的维护方案。图中仅标出了免费道路。

给定一个关于新亚王国村庄和道路的述以及国王决定保持免费的鹅卵石道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果 存在则任意输出一个方案。

输入格式

输入第一行包含三个由空格隔开的整数：

N，村庄的数目(1≤N≤20,000)；

M，道路的数目(1≤M≤100,000)；

K，国王希望保持免费的鹅卵石道路数目(0≤K≤N - 1)。

此后 M 行述了新亚王国的道路，编号分别为 1 到 M。第(i+1)行述了第 i 条 道路的情况。用 3 个由空格隔开的整数述：

ui 和 vi，为第 i 条道路连接的两个村庄的编号，村庄编号为 1 到 N；

ci，表示第 i 条道路的类型。ci = 0 表示第 i 条道路是鹅卵石路，ci = 1 表 示第 i 条道路是水泥路。

输入数据保证一对村庄之间至多有一条道路连接

输出格式

如果满足国王要求的道路维护方案不存在，你的程序应该在输出第一行打印 no solution。 否则，你的程序应该输出一个符合要求的道路维护方案，也就是保持免费的 道路列表。按照输入中给定的那样输出免费的道路。如果有多种合法方案，你可 以任意输出一种。

解题思路

本题的题面有些绕，可以理解成水泥路是免费的，而鹅卵石路是付费的，但国王可以让\(k\)条鹅卵石路免费，并且希望任意两个村庄之间都有免费道路。我们假设鹅卵石路为 1 边，水泥路为 0 边，要求总权值恰好为\(k\)的生成树。

先跑第一遍 kruscal，我们先求要使得所有的村庄连通至少要添加的鹅卵石路的数量\(cnt\)，先加水泥路再加鹅卵石路，并且将必不可少的鹅卵石路存到\(ans\)中。

如果求得的\(cnt>k\)，即必不可少的 1 边数大于\(k\)，或者此时为非连通图，则不能满足条件，输出no solution

如果满足以上条件，先重新初始化并查集并将必不可少的 1 边加入并查集中。跑第二遍 kruscal， \(cnt\)为使得所有的村庄连通最多能添加的鹅卵石路数量，先加鹅卵石路再加水泥路，将鹅卵石路继续存入\(ans\)中直到\(cnt=k\)，然后再添加水泥路。

如果最后求得的\(cnt<k\)，即最多能添加的 1 边数小于\(k\)，或者此时为非连通图，则不能满足条件，输出no solution

本题实际上不是在求最小生成树，而是总权值已经给定的生成树，所以存在多种合法方案，以上便可以求得其中一种。

#include<bits/stdc++.h>
#define IOFAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 100005;
struct node {
    int u, v, c;
};
vector<node> edge, ans;
int fa[20005], n;
int find(int x) {
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void cob(int a, int b) {
    fa[find(a)] = find(b);
}
bool count() {
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        if(fa[i] == i) cnt++;
    return cnt == 1;
}
bool cmp1(const node& a, const node& b) {
    return a.c > b.c;
}
bool cmp2(const node& a, const node& b) {
    return a.c < b.c;
}
void init() {
    for(int i = 1; i <= n; i++) fa[i] = i;
}
int main()
{
    IOFAST
    int m, k, a, b, c, cnt = 0;
    cin >> n >> m >> k;
    init();
    for(int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        edge.push_back({a, b, c});
    }
    sort(edge.begin(), edge.end(), cmp1);
    for(int i = 0; i < m; i++) {
        if(find(edge[i].u) != find(edge[i].v)) {
            cob(edge[i].u, edge[i].v);
            if(!edge[i].c) {
                cnt++;
                ans.push_back(edge[i]);
            }
        }
    }
    if(cnt > k || !count()) {
        cout << "no solution";
        return 0;
    }
    sort(edge.begin(), edge.end(), cmp2);
    cnt = 0;
    init();
    // 先将必不可少的鹅卵石路加入并查集
    for(int i = 0; i < ans.size(); i++) {
        cob(ans[i].u, ans[i].v);
        cnt++;
    }
    for(int i = 0; i < m; i++) {
        if(find(edge[i].u) != find(edge[i].v)) {
		    // 如果已经选到了k条鹅卵石路，那么将只添加水泥路
            if(edge[i].c || cnt < k) {
                cob(edge[i].u, edge[i].v);
                ans.push_back(edge[i]);
                if(!edge[i].c) cnt++;
            }
        }
    }
    if(cnt < k || !count()) cout << "no solution";
    else 
        for(int i = 0; i < ans.size(); i++) {
            printf("%d %d %d\n", ans[i].u, ans[i].v, ans[i].c);
        }
    return 0;
}