POJ 1861 Network(最小瓶颈生成树)
http://poj.org/problem?id=1861
题意:
给你一个N个点和M条边的图,现在要你从这M条边中选一些边的集合,使得单边的长度的最大值最小且所有N个点要连通.要你输出:单边长度的最大值,选的边数目,每条边的两个端点号.
分析:
其实这道题目并没有要求我们求最小生成树,只是要我们求出让图连通的最长边最短的那个值.其实这就是最小瓶颈生成树.可以用kruskal算法求出最小生成树,然后输出最后选的那条边长即可.
输出示例对于只有4个点的例子输出了4条边,没有错.因为你可以让该图有多余的边,不一定非要是树.只要连通且最长边最短就行.
注意:最后输出所有被选边的时候不能从0号边按序输出到最长的那条边.因为中间很多边可能没有被选到…
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1000+10;
const int maxm = 15000+10;
struct Edge
{
int u,v,dist;
Edge(){}
Edge(int u,int v,int d):u(u),v(v),dist(d){}
bool operator<(const Edge &rhs)const
{
return dist<rhs.dist;
}
};
struct Kruskal
{
int n,m;
Edge edges[maxm];
vector<int> E;
int fa[maxn];
int findset(int x){ return fa[x]==-1?x: fa[x]=findset(fa[x]); }
void init(int n)
{
E.clear();
this->n=n;
m=0;
memset(fa,-1,sizeof(fa));
}
void AddEdge(int u,int v,int dist)
{
edges[m++]=Edge(u,v,dist);
}
int kruskal()
{
int cnt=0;
sort(edges,edges+m);
for(int i=0;i<m;i++)
{
int u=edges[i].u, v=edges[i].v;
if(findset(u) != findset(v))
{
E.push_back(i);
fa[findset(u)] = findset(v);
if(++cnt>=n-1) return i;
}
}
return -1;
}
}KK;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
KK.init(n);
while(m--)
{
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
KK.AddEdge(u,v,d);
}
int num = KK.kruskal();
printf("%d\n",KK.edges[num].dist);
printf("%d\n",n-1);
for(int i=0;i<n-1;i++)
{
int id=KK.E[i]; //注意这里id获取有效边的编号
printf("%d %d\n",KK.edges[id].u,KK.edges[id].v);
}
return 0;
}
分享到:
相关推荐
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
利用并查集判断环路,以及快速排序计算最小生成树
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://200830740306.iteye.com/blog/603493
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1704752
北大POJ2531-Network Saboteur 解题报告+AC代码
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
poj2516代码最小费用最大流
poj 1459 Power Network.md
度限制最小生成树代码 摘自POJ1639代码
北大POJ1459-Power Network 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
poj分类poj分类poj分类poj分类
POJ题解 个人写法 线段树每个人都不一样
poj 2763 程序 线段树 LCA 2000MS AC
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告