题目描述
某个局域网内有 $n$ 台计算机和 $k$ 条 双向 网线，计算机的编号是 $1 ∼ n$。由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。
注意：
- 对于某一个连接，虽然它是双向的，但我们不将其当做回路。本题中所描述的回路至少要包含两条不同的连接。
- 两台计算机之间最多只会存在一条连接。
- 不存在一条连接，它所连接的两端是同一台计算机。
因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用 $f(i,j)$ 表示 $i,j$ 之间连接的畅通程度，$f(i,j)$ 值越小表示 $i,j$ 之间连接越通畅。
现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路且不影响连通性（即如果之前某两个点是连通的，去完之后也必须是连通的），并且被除去网线的 $\sum f(i,j)$ 最大，请求出这个最大值。
输入格式
第一行两个正整数 $n,k$。
接下来的 $k$ 行每行三个正整数 $i,j,m$ 表示 $i,j$ 两台计算机之间有网线联通，通畅程度为 $m$。
输出格式
一个正整数，表示被除去网线的 $\sum f(i,j)$ 的最大值。
数据范围
$1 \leq n \leq 100$
$0 \leq k \leq 200$
$1 \leq f(i,j) \leq 1000$
输入样例：
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
输出样例：
8
算法1
(prim) $\mathcal O(n ^ 2)$
题意：给定一张有 $n$ 个点，$k$ 条边的无向有环图。要求删掉其中部分边，且不改变图的连通性的情况下，使图中无环且所删边和最大，输出最大的所删边边权权和。
删边权和最大 $\rightarrow$ 剩下边权和最小 $\rightarrow$ 求最小生成树
但是题中并没有说图一定联通，这让这道题恶心了很多。
图不连通，就要先求出连通块，然后对每个连通块，求出其最小生成树。
当然，更巧妙的算法是用 $kruskal$，但是用 $kruskal$ 的题解太多了，这里给出 $prim$ 的代码。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 205;
int n, k; // n 为图中点数，k 为图中边数
int total; // 存图上所有边的权值总和
int g[N][N]; // prim 存图用的邻接矩阵
vector<int> dcc[N]; // 存所有的连通块
int dcc_cnt; // 存连通块的数量
int dist[N]; // prim 存到每个点最近的距离用的 dist
bool st[N]; // 一个 st 两用，先用于求连通块，再在 prim 里面每个点是否在生成树中
void dfs(int u) // dfs 求出所有的连通块
{
st[u] = true; // 先将 u 制成 true，表示已经加入已有连通块中了
dcc[dcc_cnt].push_back(u); // 将点 u 放入该连通块
for (int i = 1; i <= n; i ++ ) // 从 1 到 n 枚举所有点
if (g[u][i] < 0x3f3f3f3f && !st[i]) // 如果该点 i 能从 u 走过去，且没加入已有连通块中
dfs(i); // 那么搜索点 i
}
int prim(int u) // prim 求连通块 u 中的最小生成树
{
int res = 0; // res 记录生成树的大小
memset(dist, 0x3f, sizeof dist); // 将 dist 制为正无穷
memset(st, false, sizeof st); // 由于要多次使用 st，所以每次要先将 st 制成 false
for (int i = 0; i < dcc[u].size(); i ++ ) // 扩展 dcc[u].size() 次
{
int t = -1;
for (int j = 0; j < dcc[u].size(); j ++ ) // 枚举一下当前连通块 u 中所有点
{
int ver = dcc[u][j]; // 将该点取出
if (!st[ver] && (t == -1 || dist[t] > dist[ver])) // 如果该点不在生成树中且到该点的距离大于到点 t 的距离
t = ver; // 那么让将 t 改为该点
}
if (i) res += dist[t]; // res 加上到已有生成树中距离最近的点到已有生成树的距离
st[t] = true; // 将该点 t 加入已有生成树
for (int j = 0; j < dcc[u].size(); j ++ ) // 更新当前连通块中所有点
{
int ver = dcc[u][j]; // 将该点取出
dist[ver] = min(dist[ver], g[t][ver]);// 更新该点距离
}
}
return res; // 返回该生成树的大小
}
int main()
{
scanf("%d%d", &n, &k);
memset(g, 0x3f, sizeof g); // 将图中所有边的距离初始化为正无穷
for (int i = 0; i < k; i ++ ) // 读入图
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
total += c;
}
for (int i = 1; i <= n; i ++ ) // 枚举所有点，求连通块
if (!st[i]) // 如果该点没有加入已有的任何联通块
{
dcc_cnt ++ ; // 那么建立一个新的连通块
dfs(i); // 将该点及该点能到的所有点加入新建的连通块
}
for (int i = 1; i <= dcc_cnt; i ++ ) // 枚举所有连通块，求出所有连通块的最小生成树
total -= prim(i); // 总权值和减去该最小生成树的大小
printf("%d\n", total); // 输出剩下的权值和
return 0;
}
这题应该不需要求连通块直接标记就可
有道理啊
赞
为啥我这范围开大点就过了，但是实际上没有用这么多点啊,？？？
用的是prim的板子
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N = 110, M = 410;
int n, k;
int res1, res2;
int dist[N];
bool st[N];
int e[M], ne[M], h[N], idx, w[M];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int prim()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; i )
{
int t = -1;
for(int j = 1; j <= n; j )
{
if(!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
}
st[t] = true;
if(dist[t] != 0x3f3f3f3f) res2 += dist[t];
}
int main()
{
cin >> n >> k;
memset(h, -1, sizeof h);
while(k –)
{
int a, b, c;
scanf(“%d%d%d”, &a, &b, &c);
add(a, b, c), add(b, a, c);
res1 += c;
}
}
感觉直接判断如果$!st[i]$那就跑$prim$更简单一些
for (int i = 1; i <= dcc_cnt; i ++ ) 请问这里为什么不是从 0~dcc_cnt-1 而是 1~dcc_cnt 呢……
求联通快的时候，我是先
dcc_cnt ++，再dfs的，所以联通快的编号是从1开始的tql
用并查集求连通块要简单点吧
并查集求连通块嘛，那个时间复杂度貌似要带个log？
我不太会，抱歉，wtcl
tql
随手赞一个
学习学习 ORZ
tql