POJ 1797 Heavy Transportation(最大生成树)
http://poj.org/problem?id=1797
题意:
求1号点s到n号点t的可行路径上最小值的最大值(有点拗口)也就是说从s到t的每一条可行路径上都有一条单段边的最小值,有多条路径的话就求这些最小值的最大值。
分析:
本题和POJ2263很像:http://blog.csdn.net/u013480600/article/details/37739209.
本题最直观的做法是用并查集+二分试探.还可以用Floyd的动态规划思想做,也可以用dijkstra算法来做.这里我们用最大生成树思想来做.
其实就是将所有边按大到小排序,然后我们依次将边加入图中,当1号点和n号点第一次连通的时候,加入的边就是从1到n路径上的承重量的最大值.(想想为什么)
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
const int maxm=1000*1000+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];
int fa[maxn];
int findset(int x){return fa[x]==-1? x:fa[x]=findset(fa[x]); }
void init(int n)
{
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()
{
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))
{
fa[findset(u)] = findset(v);
if(findset(1) == findset(n)) return edges[i].dist;
}
}
return -1;
}
}KK;
int main()
{
int T; scanf("%d",&T);
for(int kase=1;kase<=T;kase++)
{
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);
}
printf("Scenario #%d:\n%d\n\n",kase,KK.kruskal());
}
return 0;
}
分享到:
相关推荐
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1705139
NULL 博文链接:https://200830740306.iteye.com/blog/603493
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1704752
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj openjudge 1111题最大正向匹配 提交ac
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
POJ题解 个人写法 线段树每个人都不一样
北大POJ1159-Palindrome 解题报告+AC代码
poj 2763 程序 线段树 LCA 2000MS AC
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类