算法竞赛入门经典（紫书） 第十一章题解

开始刷紫书第十一章图论，刷题之路十分艰难，只因我菜的深沉。

例题11-2
思路：kruskal 枚举边的起点，生成了最小生成树以后更新答案，立马换另一个起点进行枚举。

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
const int maxn = 105;
const int maxm = 1e5 + 5;
struct node
{
int u, v, w;
}e[maxm];
bool cmp(node n1, node n2)
{
if (n1.w == n2.w) return n1.u < n2.u;
return n1.w < n2.w;
}
int par[maxn];
void init()
{
for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int v)
{
if (v == par[v]) return v;
par[v] = find(par[v]);
return par[v];
}
void unite(int u, int v)
{
int fu = find(u);
int fv = find(v);
if (fu == fv) return;
par[fv] = fu;
}
int kruskal()
{
int cnt;
int ans=0x3f3f3f3f;
int maxe, mine;
for (int L = 1; L <= m; L++) {
init();
cnt = 0;
maxe = -1, mine = 0x3f3f3f3f;
for (int i = L; i <= m; i++)
{
int u = e[i].u, v = e[i].v;
int fu = find(u);
int fv = find(v);
if (fu != fv)
{
if (e[i].w > maxe) maxe = e[i].w;
if (e[i].w < mine) mine = e[i].w;
unite(fu, fv);
cnt++;
}
if (cnt == n - 1) {
if(maxe-mine<ans) ans = maxe-mine;
break;
}
}
}
if (ans >= 0x3f3f3f3f) return -1;
return ans;
}
int main()
{
while (~scanf("%d %d", &n, &m))
{
if (n == 0 && m == 0) break;
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
}
sort(e + 1, e + 1 + m, cmp);
printf("%dn", kruskal());
}
}

例题11-3
思路：先跑一遍最小生成树，确定好用哪些边，再枚举购买的套餐方案，等价于把套餐里的方案变为0，原来就是一个会被使用的 小边，现在边的更小，所以还是使用这条边，连接的边不会因为套餐而改变。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;//点数 套餐数
vector <int> v[3010];
int par[3010];
struct Point
{
int x, y;
}p[3010];
struct Edge
{
int u, v, w;
}e[2002000],E[3010];
int id;
int useid;
bool cmp(Edge e1, Edge e2)
{
if (e1.w == e2.w) return e1.u < e2.u;
return e1.w < e2.w;
}
void init()
{
for (int i = 1; i <= n; i++) par[i] = i;
}
int find(int v)
{
if (v == par[v]) return v;
par[v] = find(par[v]);
return par[v];
}
void unite(int u, int v)
{
int fu = find(u);
int fv = find(v);
if (fu == fv) return;
par[fv] = fu;
}
int kruskal()
{
init();
int ans = 0;
for (int i = 1; i <= id; i++)
{
int u = e[i].u;
int v = e[i].v;
int fu = find(u);
int fv = find(v);
if (fu != fv)
{
E[++useid] = e[i];
unite(u, v);
//cout << i<<" "<<u << " " << v << endl;
ans += e[i].w;
}
}
return ans;
}
int solve()
{
int ans = 0;
for (int i = 1; i <= useid; i++)
{
int u = E[i].u;
int v = E[i].v;
int fu = find(u);
int fv = find(v);
if (fu != fv)
{
unite(u, v);
ans += E[i].w;
}
}
return ans;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
useid = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
v[i].clear();
int num, money;
scanf("%d%d", &num, &money);
v[i].push_back(money);//把费用记录在0的位置
for (int j = 1; j <= num; j++)
{
int point;
scanf("%d", &point);
v[i].push_back(point);
}
}
id = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
for (int j = 1; j < i; j++)
{
e[++id].u = j;
e[id].v = i;
e[id].w = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
}
}
//cout << "id:" << id << endl;
sort(e + 1, e + 1 + id, cmp);
int ans=kruskal();
int sub = 0;
for (int i = 0; i < (1 << m); i++)//枚举哪些套餐要买
{
init();
int j = i;
int sum = 0;
int p = 1;
while (j)
{
int p1;
bool flag = true;
if (j & 1)
{
if (flag) {
p1 = v[p][1]; flag = false;
}
sum += v[p][0];
for (int k = 1; k < v[p].size(); k++)
{
int u = v[p][k];
if (p1 == u) continue;
if (find(p1) == find(u)) continue;
unite(p1, u);
}
}
p++;
j >>= 1;
}
sum+=solve();
if (sum < ans) ans = sum;
}
printf("%dn", ans);
if(t) printf("n");
}
}

最后

以上就是干净雪糕为你收集整理的算法竞赛入门经典（紫书） 第十一章题解的全部内容，希望文章能够帮你解决算法竞赛入门经典（紫书） 第十一章题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。