bzoj1064
2024-10-14 04:03:08
很巧妙的题
首先有几种情况
1. 有环 2.两点间有多条路径 3.其他
3.显然最简单,最小是3,最大是每个弱联通块中最长链
2.显然,两点间两条路径的差是答案的倍数
1.出现环,那答案一定是其约数,那么最大答案就是所有环长的最大公约数,最小是最大的大于等于3的最小因数
综合以上,我们就有了大概的思路,但是不好处理
有一个精妙的做法,对于每条边添加一个长度为-1的反向边,一下就简单多了
type node=record
po,next,num:longint;
end; var e:array[..] of node;
p,d:array[..] of longint;
v:array[..] of boolean;
mi,i,l,r,n,m,len,ans,x,y:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function gcd(a,b:longint):longint;
begin
if b= then exit(a)
else exit(gcd(b,a mod b));
end; procedure add(x,y,z:longint);
begin
inc(len);
e[len].po:=y;
e[len].num:=z;
e[len].next:=p[x];
p[x]:=len;
end; procedure dfs(x:longint);
var i,y:longint;
begin
v[x]:=true;
i:=p[x];
while i<>- do
begin
y:=e[i].po;
if v[y] then ans:=gcd(ans,abs(d[x]+e[i].num-d[y]))
else begin
d[y]:=d[x]+e[i].num;
dfs(y);
end;
i:=e[i].next;
end;
end; procedure find(x:longint);
var i,y:longint;
begin
v[x]:=true;
l:=min(l,d[x]);
r:=max(r,d[x]);
i:=p[x];
while i<>- do
begin
y:=e[i].po;
if not v[y] then
begin
d[y]:=d[x]+e[i].num;
find(y);
end;
i:=e[i].next;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m);
for i:= to m do
begin
readln(x,y);
add(x,y,);
add(y,x,-);
end;
for i:= to n do
if not v[i] then dfs(i);
if ans<> then
begin
mi:=ans;
for i:= to ans do
if ans mod i= then
begin
mi:=i;
break;
end;
end
else begin
fillchar(v,sizeof(v),false);
for i:= to n do
if not v[i] then
begin
d[i]:=;
l:=; r:=;
find(i);
ans:=ans+r-l+;
end; mi:=;
end;
if ans< then writeln('-1 -1') else writeln(ans,' ',mi);
end.
最新文章
- OpenGL超级宝典visual studio 2013开发环境配置,GLTools
- .NET: WPF Data Binding
- GitHub托管
- 安装GeoIP数据库
- 小胖说事24-----property&;#39;s synthesized getter follows Cocoa naming convention for returning &;#39;owned&;#39; objec
- C#开发157
- Python 常见的内置模块
- activemq的安装与使用
- Lua脚本在redis分布式锁场景的运用
- Windows2016的 IIS中配置PHP7运行环境
- mysql5.5 五种日期
- 吴恩达机器学习笔记4-代价函数III(cost function)
- 图像特征的提取(gaussian,gabor,frangi,hessian,Morphology...)及将图片保存为txt文件
- Zabbix监控Tomcat案例
- 为什么Firefox在SSH上这么慢?
- (PMP)第10章-----项目沟通管理
- HTML5 defer和async的区别
- 可跨平台C++开源图形图像框架:openFrameworks
- [SpringMVC+redis]自定义aop注解实现控制器访问次数限制
- mysql case的语法
热门文章
- 在myeclipse中使用Java语言进行spark Standalone模式应用程序开发
- InnoDB与UUID
- 如何在Eclipse中配置Tomcat服务器
- NuGet使用简要说明
- 无废话网页重构系列——(6)HTML主干结构:站点(site)、页面(page)
- UVALive 6533
- HDU4804 Campus Design 轮廓线dp
- POJ1258Agri-Net
- mysql 中 isnull 和 ifnull 判断字段是否为null
- java.lang.NoClassDefFoundError: JspException