题意理解了就很好做

题意:给一张无向图,任意取两个点s,t,s->t的路径上必经边数量为k

求这样的s,t,使得k最大

#include<bits/stdc++.h>
#define maxn 300005
using namespace std;
struct Edge{int to,nxt,b;}e[maxn<<],e_c[maxn<<];
int head[maxn],tot,head_c[maxn],tot_c,n,m;
void init(){
memset(head,-,sizeof head);
memset(head_c,-,sizeof head_c);
tot=tot_c=;
}
void add(int u,int v){
e[tot].to=v;e[tot].nxt=head[u];head[u]=tot++;
}
void add_c(int u,int v){
e_c[tot_c].to=v;e_c[tot_c].nxt=head_c[u];head_c[u]=tot_c++;
} int ind,low[maxn],dfn[maxn];
void tarjan(int x,int in_edge){
low[x]=dfn[x]=++ind;
for(int i=head[x];i!=-;i=e[i].nxt){
int y=e[i].to;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x])
e[i].b=e[i^].b=;
}
else if(i!=(in_edge^))
low[x]=min(low[x],dfn[y]);
}
}
int c[maxn],dcc;
void dfs1(int x){
c[x]=dcc;
for(int i=head[x];i!=-;i=e[i].nxt){
int y=e[i].to;
if(e[i].b || c[y]!=)continue;
dfs1(y);
}
} int dp[maxn],ans;
void dfs2(int x,int pre){
for(int i=head_c[x];i!=-;i=e_c[i].nxt){
int y=e_c[i].to;
if(y==pre)continue;
dfs2(y,x);
ans=max(ans,dp[x]+dp[y]+);
dp[x]=max(dp[x],dp[y]+);
}
} int main(){
init();
cin>>n>>m;int u,v;
for(int i=;i<=m;i++){
cin>>u>>v;
add(u,v);add(v,u);
}
tarjan(,-); for(int i=;i<=n;i++)
if(!c[i]){
++dcc;
dfs1(i);
} for(int i=;i<tot;i++){
int x=e[i].to,y=e[i^].to;
if(c[x]!=c[y])
add_c(c[x],c[y]);
} dfs2(,); cout<<ans<<'\n';
}

最新文章

  1. webService学习之路(三):springMVC集成CXF后调用已知的wsdl接口
  2. SQL添加维护 计划失败
  3. 你不知道的this—JS异步编程中的this
  4. Euclidean Space
  5. 。。。再战JQuery。。。
  6. sublime text2 解决中文乱码
  7. 《OD学hadoop》第一周0626
  8. 关于css中z-index 的应用
  9. opencv2使用形态学滤波对图像进行边缘及角点检測
  10. java7 语法糖 之 switch 声明string
  11. [flask/python/web] 解析flask web开发(Miguel著)一书第11章主页不显示博文表单的问题
  12. pwd
  13. 启动期间的内存管理之初始化过程概述----Linux内存管理(九)
  14. Queue的相关API
  15. BZOJ.3926.[ZJOI2015]诸神眷顾的幻想乡(广义后缀自动机)
  16. Office365 OneDrive Geo Move
  17. vue-cli 搭建的项目处理不同环境下请求不同域名的问题
  18. moco入门
  19. 转:Jquery的parent和parents(找到某一特定的祖先元素)
  20. Digital Image Processing 学习笔记1

热门文章

  1. 2018-2-13-win10-uwp-入门
  2. centos6和7安装vnc
  3. 读书笔记---《Docker 技术入门与实践》---为镜像添加SSH服务
  4. C—变量—register
  5. 2.Struts2配置文件
  6. 快速失败and安全失败
  7. 网络编程之TCP协议怎么使用?
  8. 累乘函数线性逆元打表,阶乘反演——bzoj4816
  9. Go 程序开发的注意事项
  10. hdu4352-XHXJ&#39;s LIS状压DP+数位DP