这题的思路就是找一个范围,看看这个范围是否可行
主流是二分Ans,我是先把点排序,求最小生成树检查首位的
Program P2110;
type
ed=record
u,v,w:longint;
end;
var
a:array[1..120,1..120] of longint;
edge:array[0..30000] of ed;
n,i,j,size,ans:longint;
now:longint;
father:array[0..10001] of longint;
b:array[0..121,0..121] of boolean;
procedure add(u,v,w:longint);
begin
inc(size);
edge[size].u:=u;
edge[size].v:=v;
edge[size].w:=w;
end;
procedure qsort(l,r:longint);
var
i,j,m:longint;
p:ed;
begin
i:=l;
j:=r;
m:=edge[(l+r) shr 1].w;
repeat
while edge[i].w<m do inc(i);
while edge[j].w>m do dec(j);
if i<=j then
begin
p:=edge[i];
edge[i]:=edge[j];
edge[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function getfather(x:longint):longint;
begin
if x=father[x] then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
function hash(x,y:longint):longint;
begin
exit((x-1)*n+y);
end;
begin
size:=0;
read(n);
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
add(i,j,a[i,j]);
end;
// (0,n*n)
qsort(1,size);
edge[0].w:=edge[1].w-1;
ans:=110;
// writeln;
for i:=1 to size do
begin
if edge[i].w=edge[i-1].w then continue;
for j:=0 to n*n do father[j]:=j;
fillchar(b,sizeof(b),false);
for j:=i to size do
begin
b[edge[j].u,edge[j].v]:=true;
now:=hash(edge[j].u,edge[j].v);
if b[edge[j].u-1,edge[j].v] then
if getfather(now)<>getfather(now-n) then
begin
father[father[now]]:=father[father[now-n]];
if getfather(0)=getfather(n*n) then break;
end;
if b[edge[j].u+1,edge[j].v] then
if getfather(now)<>getfather(now+n) then
begin
father[father[now]]:=father[father[now+n]];
if getfather(0)=getfather(n*n) then break;
end;
if b[edge[j].u,edge[j].v+1] then
if getfather(now)<>getfather(now+1) then
begin
father[father[now]]:=father[father[now+1]];
if getfather(0)=getfather(n*n) then break;
end;
if b[edge[j].u,edge[j].v-1] then
if getfather(now)<>getfather(now-1) then
begin
father[father[now]]:=father[father[now-1]];
if getfather(0)=getfather(n*n) then break;
end;
if getfather(1)=getfather(n*n) then break;
end;
if getfather(1)<>getfather(n*n) then break;
if ans>edge[j].w-edge[i].w then ans:=edge[j].w-edge[i].w;
end;
writeln(ans);
end.
分享到:
相关推荐
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1704752
NULL 博文链接:https://128kj.iteye.com/blog/1705139
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
度限制最小生成树代码 摘自POJ1639代码
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 //表示举例 非主流...
利用并查集判断环路,以及快速排序计算最小生成树
北大2485的简单题目。用了最小生成树,在VS上编译,并成功提交。
(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) .....
acm code of 20053565 poj onlinejudge 高精度 DP 图论 算法 最大流 最小生成树 线段树
通过学习STL中的队列的实现原理解决了一道应用题:北大poj网上的Catch That Cow题目。还有最小生成树的应用的课程设计
Algorithm-Java Algorithms + Data Structures = Programs. ——Niklaus Wirth 没日没夜地写程序。看到这几个字我两眼一黑,仿佛这就是我未来的生活。 为了摆脱这种焦虑心理,我逐步...最小生成树(prim,kruskal)(p
虽然A过了觉得简单,但要注意点小问题,而且我哇的时候没有找到解题报告,所以希望能对没A的人有点小帮助
4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya 定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 1、 排序 2、 搜索、回溯、...
2.最小生成树(先写个prim,kruscal要用并查集,不好写) 3.大数(高精度)加减乘除 4.二分查找. (代码可在五行以内) 5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简) ...
8.8 最小生成树(kruskal) 172 8.9 最短路径 173 8.10 最大网络流 175 8.11 最小费用流 180 8.12 最大团问题 182 8.13 二分图匹配 184 8.14 带权的最优二分图匹配 184 9.搜索算法概略 187 9.1 迭代深搜+IDA* 187 9.2 ...
2.5.5 最小生成树 2.5.6 应用问题 2.6 数学问题的解题窍门 2.6.1 辗转相除法 2.6.2 有关素数的基础算法 2.6.3 模运算 2.6.4 快速幂运算 2.7 一起来挑战GCJ的题目(1) 2.7.1 Minimum Scalar Product 2.7.2 Crazy ...
2.6 随机素数测试和大数分解 (POJ 1811) . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.1 分解质因素求...