首页 > 代码库 > NYOJ 118 修路方案
NYOJ 118 修路方案
修路方案
时间限制：3000 ms | 内存限制：65535 KB
难度：5
- 描述
南将军率领着许多部队，它们分别驻扎在N个不同的城市里，这些城市分别编号1~N，由于交通不太便利，南将军准备修路。
现在已经知道哪些城市之间可以修路，如果修路，花费是多少。
现在，军师小工已经找到了一种修路的方案，能够使各个城市都联通起来，而且花费最少。
但是，南将军说，这个修路方案所拼成的图案很不吉利，想让小工计算一下是否存在另外一种方案花费和刚才的方案一样，现在你来帮小工写一个程序算一下吧。
- 输入
- 第一行输入一个整数T(1<T<20)，表示测试数据的组数
每组测试数据的第一行是两个整数V,E，(3<V<500,10<E<200000)分别表示城市的个数和城市之间路的条数。数据保证所有的城市都有路相连。
随后的E行，每行有三个数字A B L，表示A号城市与B号城市之间修路花费为L。 - 输出
- 对于每组测试数据输出Yes或No（如果存在两种以上的最小花费方案则输出Yes,如果最小花费的方案只有一种，则输出No)
- 样例输入
23 31 2 12 3 23 1 34 41 2 22 3 23 4 24 1 2
- 样例输出
NoYes
- 来源
- POJ题目改编
- 上传者
- 张云聪
解题：次小生成树，搞了好久，好多文档看不懂啊。。。只好学点奇葩的东西，走点旁门左道了。。。。。弱菜有弱菜的学习方法。。。
这是什么算法。。。？好吧。。。偷学于豆丁上一篇文章<<A-star和第k短路和次小生成树和Yen和MPS寻路算法>>
首先求出原图的最小生成树，记录权值之和为Minst.枚举添加每条不在最小生成树上的边<u,v>，加上以后一定会形成一个环，找到环上权值第二大的边（即除<u,v>外最大的边）把它删除掉，计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值，就是次小生成树。具体实现时，更简单的方法是从每个节点i遍历整个最小生成树，定义F[j]为从i到j的路径上最大边的权值。遍历图求出F[j]的值，然后对于添加每条不在最小生成树中的边<i,j>，新的生成树权值之和就是Minst-w<i,j>-F[j],记录其最小值，则为次小生成树。该算法的时间复杂度为O(n^2+m)。由于只用求一次最小生成树，可以用最简单的Prim算法，时间复杂度为O(n^2)。算法的瓶颈不在于最小生成树，而在于O(n^2+m)的枚举加边修改，所以用更好的最小生成树算法是没有必要的。
View Code1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 #define INF 0x3f3f3f11 using namespace std;12 struct arc {13 int u,v,w;14 } e[200010];15 int mp[501][501],d[501],pre[501],uf[501];16 int n,m;17 bool vis[200010];18 bool cmp(const arc &x,const arc &y){19 return x.w < y.w;20 }21 int findF(int x){22 if(x != uf[x])23 uf[x] = findF(uf[x]);24 return uf[x];25 }26 int kruskal(){27 int i,j,ans = 0;28 for(i = 1; i <= n; i++){29 uf[i] = i;30 pre[i] = -1;31 }32 memset(vis,false,true);33 for(i = 0; i < m; i++){34 int x = findF(e[i].u);35 int y = findF(e[i].v);36 if(x != y){37 uf[x] = y;38 ans += e[i].w;39 pre[e[i].v] = e[i].u;40 vis[i] = true;41 }42 }43 return ans;44 }45 int main() {46 int ks,i,j,Minst,mx,u,v;47 bool flag;48 scanf("%d",&ks);49 while(ks--) {50 scanf("%d%d",&n,&m);51 for(i = 0; i < m; i++) {52 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);53 if(e[i].u > e[i].v) swap(e[i].u,e[i].v);54 mp[e[i].u][e[i].v] = mp[e[i].v][e[i].u] = e[i].w;55 }56 sort(e,e+m,cmp);57 Minst = kruskal();58 flag = false;59 for(i = 0; i < m; i++){60 if(!vis[i]){61 mx = 0;62 u = e[i].u;63 v = e[i].v;64 while(pre[v] != u && pre[v] != -1){65 if(mp[v][pre[v]] > mx) mx = mp[v][pre[v]];66 v = pre[v];67 }68 if(mx == e[i].w){69 flag = true;break;70 }71 }72 }73 flag?puts("Yes"):puts("No");74 }75 return 0;76 }
别人写的Prim算法版的次小生成树View Code1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 #define maxN 510 6 #define MAX 0x0fffffff 7 #define MIN -0x0fffffff 8 int N,M,map[maxN][maxN],dis[maxN],maxlen[maxN][maxN],pre[maxN]; 9 bool vis[maxN];10 int prim() {11 int i,j,k,minn,pr;12 memset(vis,false,sizeof(vis));13 for(i=1; i<=N; i++) {14 dis[i]=map[1][i];15 pre[i]=1;16 }17 vis[1]=true;18 for(j=1; j<N; j++) {19 minn = MAX;20 for(i=1; i <= N; i++)21 if(!vis[i] && dis[i]<minn) {22 minn=dis[k=i];23 }24 pr = pre[k];25 maxlen[k][pr] = maxlen[pr][k] = map[k][pr];26 for(i = 1; i <= N; i++)27 if(vis[i])28 maxlen[i][k]=maxlen[k][i]=max(maxlen[i][pr],maxlen[pr][k]);29 vis[k]=true;30 for(i=1; i<=N; i++)31 if(!vis[i]&&dis[i]>map[k][i]) {32 dis[i]=map[i][k];33 pre[i]=k;34 }35 }36 for(i=1; i < N; i++)37 for(j = i+1; j <= N; j++)38 if(pre[i] == j|| pre[j] == i) continue;39 else if(maxlen[i][j] == map[i][j]) return 1;40 return 0;41 }42 int main() {43 int T;44 scanf("%d",&T);45 while(T--) {46 int u,v,w;47 scanf("%d%d",&N,&M);48 for(int i = 0; i <= N; i++)49 for(int j=0; j <= N; j++) {50 map[i][j] = MAX;51 maxlen[i][j] = MIN;52 }53 for(int i = 0; i < M; i++) {54 scanf("%d%d%d",&u,&v,&w);55 map[u][v]=map[v][u]=w;56 }57 if(prim())printf("Yes\n");58 else printf("No\n");59 }60 return 0;61 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。