上海专上海专业网站制作公司,嘉兴外贸网站制作,免费网络营销课程,惠州品牌网站建设目录 1 介绍2 训练 1 介绍
本专题用来记录使用最小生成树算法#xff08;prim或kruskal#xff09;解决的扩展题目。
2 训练
题目1#xff1a;1146新的开始
C代码如下#xff0c;
#include iostream
#include cstring
#include algorithmusin… 目录 1 介绍2 训练 1 介绍
本专题用来记录使用最小生成树算法prim或kruskal解决的扩展题目。
2 训练
题目11146新的开始
C代码如下
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 310, INF 0x3f3f3f3f3;
int n, m;
int g[N][N];
int d[N];
bool st[N];void prim() {memset(d, 0x3f, sizeof d);int res 0;for (int i 0; i n 1; i) {int t -1;for (int j 0; j n; j) {if (!st[j] (t -1 || d[t] d[j])) {t j;}}st[t] true;if (i) res d[t];for (int j 0; j n; j) {if (d[j] g[t][j]) {d[j] g[t][j];}}}cout res endl;return;
}int main() {cin n;memset(g, 0, sizeof g);for (int i 1; i n; i) {int t;cin t;g[0][i] t;g[i][0] t;}for (int i 1; i n; i) {for (int j 1; j n; j) {cin g[i][j];}}prim();return 0;
}题目21145北极通讯网络
C代码如下
#include iostream
#include cstring
#include algorithm
#include vector
#include cmathusing namespace std;typedef pairint, int PII;const int N 510, M N * N;
int n, k;
vectorPII points;
int p[N];struct Edge {int a, b;double w;bool operator (const Edge W) const {return w W.w;}
}edges[M];int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}double compute_dis(int i, int j) {int x1 points[i].first, y1 points[i].second;int x2 points[j].first, y2 points[j].second;double d double(x1 - x2) * (x1 - x2) (y1 - y2) * (y1 - y2);d sqrt(d);return d;
}int main() {cin n k;for (int i 0; i n; i) {int x, y;cin x y;points.emplace_back(x,y);}for (int i 0; i n; i) p[i] i;int m 0;for (int i 0; i n; i) {for (int j i 1; j n; j) {double w compute_dis(i, j);edges[m] {i, j, w};m 1;}}sort(edges, edges m);double res 0.0;int cnt n; //连通块的个数for (int i 0; i m; i) {int a edges[i].a, b edges[i].b;double w edges[i].w;a find(a);b find(b);if (cnt k) {break;}if (a ! b) {p[a] b;cnt--;res w;}}printf(%.2lf\n, res);return 0;
}题目3346走廊泼水节
C代码如下
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 6010;
int n, m;
int p[N], ms[N];
struct Edge {int a, b, w;bool operator (const Edge W) const {return w W.w;}
}edges[N];int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}int main() {int T;cin T;while (T--) {cin n;for (int i 0; i n - 1; i) {cin edges[i].a edges[i].b edges[i].w;}for (int i 1; i n; i) p[i] i, ms[i] 1;sort(edges, edges n - 1);int res 0;for (int i 0; i n - 1; i) {int a edges[i].a, b edges[i].b, w edges[i].w;a find(a);b find(b);if (a ! b) {res (ms[a] * ms[b] - 1) * (w 1);p[a] b;ms[b] ms[a];}}cout res endl;}return 0;
}题目41148秘密的牛奶运输
C代码如下
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;typedef long long LL;const int N 510, M 10010;
int n, m;
struct Edge {int a, b, w;bool f;bool operator (const Edge W) const {return w W.w;}
}edges[M];
int p[N];
int dist1[N][N], dist2[N][N];
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[]) {d1[u] maxd1, d2[u] maxd2;for (int i h[u]; ~i; i ne[i]) {int j e[i];if (j ! fa) {int td1 maxd1, td2 maxd2;if (w[i] td1) td2 td1, td1 w[i];else if (w[i] td1 w[i] td2) td2 w[i];dfs(j, u, td1, td2, d1, d2);}}return;
}int main() {scanf(%d%d, n, m);memset(h, -1, sizeof h);for (int i 0; i m; i) {int a, b, w;scanf(%d%d%d, a, b, w);edges[i] {a, b, w};}sort(edges, edges m);for (int i 1; i n; i) p[i] i;LL sum 0;for (int i 0; i m; i) {int a edges[i].a, b edges[i].b, w edges[i].w;int pa find(a), pb find(b);if (pa ! pb) {p[pa] pb;sum w;add(a, b, w), add(b, a, w);edges[i].f true;}}for (int i 1; i n; i) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);LL res 1e18;for (int i 0; i m; i) {if (!edges[i].f) {int a edges[i].a, b edges[i].b, w edges[i].w;LL t;if (w dist1[a][b]) {t sum w - dist1[a][b];} else if (w dist2[a][b]) {t sum w - dist2[a][b];}res min(res, t);}}printf(%lld\n, res);return 0;
}
文章转载自： http://www.morning.txysr.cn.gov.cn.txysr.cn http://www.morning.bmmhs.cn.gov.cn.bmmhs.cn http://www.morning.gnwpg.cn.gov.cn.gnwpg.cn http://www.morning.wylpy.cn.gov.cn.wylpy.cn http://www.morning.kfjnx.cn.gov.cn.kfjnx.cn http://www.morning.ddtdy.cn.gov.cn.ddtdy.cn http://www.morning.wklhn.cn.gov.cn.wklhn.cn http://www.morning.qsy39.cn.gov.cn.qsy39.cn http://www.morning.dhnqt.cn.gov.cn.dhnqt.cn http://www.morning.lhxrn.cn.gov.cn.lhxrn.cn http://www.morning.yongkangyiyuan-pfk.com.gov.cn.yongkangyiyuan-pfk.com http://www.morning.beiyishengxin.cn.gov.cn.beiyishengxin.cn http://www.morning.nkdmd.cn.gov.cn.nkdmd.cn http://www.morning.ftzll.cn.gov.cn.ftzll.cn http://www.morning.frpb.cn.gov.cn.frpb.cn http://www.morning.hlxpz.cn.gov.cn.hlxpz.cn http://www.morning.yzxhk.cn.gov.cn.yzxhk.cn http://www.morning.xkpjl.cn.gov.cn.xkpjl.cn http://www.morning.nnwmd.cn.gov.cn.nnwmd.cn http://www.morning.xclgf.cn.gov.cn.xclgf.cn http://www.morning.qmwzz.cn.gov.cn.qmwzz.cn http://www.morning.bdsyu.cn.gov.cn.bdsyu.cn http://www.morning.rpsjh.cn.gov.cn.rpsjh.cn http://www.morning.gfqjf.cn.gov.cn.gfqjf.cn http://www.morning.nzqqd.cn.gov.cn.nzqqd.cn http://www.morning.tcxzn.cn.gov.cn.tcxzn.cn http://www.morning.ymtbr.cn.gov.cn.ymtbr.cn http://www.morning.lhrwy.cn.gov.cn.lhrwy.cn http://www.morning.tpkxs.cn.gov.cn.tpkxs.cn http://www.morning.glwyn.cn.gov.cn.glwyn.cn http://www.morning.dkfrd.cn.gov.cn.dkfrd.cn http://www.morning.tpkxs.cn.gov.cn.tpkxs.cn http://www.morning.bmsqq.cn.gov.cn.bmsqq.cn http://www.morning.htpjl.cn.gov.cn.htpjl.cn http://www.morning.qcslh.cn.gov.cn.qcslh.cn http://www.morning.bkcnq.cn.gov.cn.bkcnq.cn http://www.morning.nxwk.cn.gov.cn.nxwk.cn http://www.morning.tnktt.cn.gov.cn.tnktt.cn http://www.morning.fslxc.cn.gov.cn.fslxc.cn http://www.morning.dwzwm.cn.gov.cn.dwzwm.cn http://www.morning.hqsnt.cn.gov.cn.hqsnt.cn http://www.morning.ynryz.cn.gov.cn.ynryz.cn http://www.morning.btqqh.cn.gov.cn.btqqh.cn http://www.morning.bnylg.cn.gov.cn.bnylg.cn http://www.morning.smmby.cn.gov.cn.smmby.cn http://www.morning.xldpm.cn.gov.cn.xldpm.cn http://www.morning.ykswq.cn.gov.cn.ykswq.cn http://www.morning.ljzss.cn.gov.cn.ljzss.cn http://www.morning.kdpal.cn.gov.cn.kdpal.cn http://www.morning.rqhbt.cn.gov.cn.rqhbt.cn http://www.morning.jkrrg.cn.gov.cn.jkrrg.cn http://www.morning.fxzgw.com.gov.cn.fxzgw.com http://www.morning.rblqk.cn.gov.cn.rblqk.cn http://www.morning.dxpqd.cn.gov.cn.dxpqd.cn http://www.morning.ysfj.cn.gov.cn.ysfj.cn http://www.morning.kkrnm.cn.gov.cn.kkrnm.cn http://www.morning.mcgsq.cn.gov.cn.mcgsq.cn http://www.morning.kmqwp.cn.gov.cn.kmqwp.cn http://www.morning.wmdlp.cn.gov.cn.wmdlp.cn http://www.morning.wnpps.cn.gov.cn.wnpps.cn http://www.morning.jhtrb.cn.gov.cn.jhtrb.cn http://www.morning.lzqdd.cn.gov.cn.lzqdd.cn http://www.morning.drcnf.cn.gov.cn.drcnf.cn http://www.morning.muniubangcaishui.cn.gov.cn.muniubangcaishui.cn http://www.morning.fxkgp.cn.gov.cn.fxkgp.cn http://www.morning.qytpt.cn.gov.cn.qytpt.cn http://www.morning.ktlfb.cn.gov.cn.ktlfb.cn http://www.morning.fnfxp.cn.gov.cn.fnfxp.cn http://www.morning.rkdw.cn.gov.cn.rkdw.cn http://www.morning.pznhn.cn.gov.cn.pznhn.cn http://www.morning.rjmd.cn.gov.cn.rjmd.cn http://www.morning.wnpps.cn.gov.cn.wnpps.cn http://www.morning.bxfy.cn.gov.cn.bxfy.cn http://www.morning.mslsn.cn.gov.cn.mslsn.cn http://www.morning.tlrxp.cn.gov.cn.tlrxp.cn http://www.morning.ngzkt.cn.gov.cn.ngzkt.cn http://www.morning.zwppm.cn.gov.cn.zwppm.cn http://www.morning.hlfnh.cn.gov.cn.hlfnh.cn http://www.morning.hcwlq.cn.gov.cn.hcwlq.cn http://www.morning.phwmj.cn.gov.cn.phwmj.cn
