传送门:http://acm.hnu.cn/online/?action=problem&type=show&id=12307
题目大意:给定一个联通图,求出能有多少种不同的方式去除两个不同的点使得原图变的不联通。
关于解题:这道是上次校赛的一道题,比赛当时没仔细想,也没仔细看数据,压根就没想枚举割点,后来听解题报告的时候恍然大悟,这道题可以先用tarjan求一次割点,然后对于此次求出的割点,剩下任意的点都可以与割点构成一对(注意判重),对于非割点,那么考虑去除它,再求一次割点,这次出现的那么被去除的点与这次求出的割点同样构成一组(注意去重),那么累加起来就是结果。(PS:我这样写始终WA,于是反向思维,求出去除两个点之后图仍然连通,这样所有的点对,也就是去除非割点后,再求非割点,在用总点对数减去它就AC了)
代码:
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 555;
vector<int> g[MAXN];
int cut[2][MAXN],dfn[MAXN],low[MAXN],ans,deep,n,m,hash[MAXN][MAXN];
void tarjan(int kd,int pt,int u,int fa,int rt){
if(u==pt)return;
low[u] = dfn[u] = deep++;
int son = 0;
for(int i=0;i<(int)g[u].size();i++){
int v = g[u][i];if(v==pt)continue;
if(!dfn[v]){
son++;
tarjan(kd,pt,v,u,rt);
low[u] = min(low[u],low[v]);
if((u==rt&&son>=2)||(u!=rt&&low[v]>=dfn[u])){
cut[kd][u] = 1;
}
}else if(fa!=v){
low[u] = min(low[u],dfn[v]);
}
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<MAXN;i++)g[i].clear();
while(m--){
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
memset(dfn,0,sizeof(dfn));
memset(cut,0,sizeof(cut));
memset(hash,0,sizeof(hash));
ans = 0;
deep = 1;
tarjan(0,-1,0,-1,0);//找出所有的割点
for(int i=0;i<n;i++){
if(!cut[0][i]){//对于非割点
memset(dfn,0,sizeof(dfn));
memset(cut[1],0,sizeof(cut[1]));
deep = 1;
int rt = i==0?i+1:i-1;
tarjan(1,i,rt,-1,rt);
for(int j=0;j<n;j++){
if(!cut[1][j]&&(!hash[i][j])&&(!hash[j][i])&&j!=i){//还是非割点
hash[i][j] = hash[j][i] = 1;
ans++;
}
}
}
}
printf("%d\n",(n*(n-1)/2)-ans);
}
return 0;
}
分享到:
相关推荐
这些源代码是参赛者在解决HOJ平台上的算法问题时编写的,旨在展示不同问题的解决思路和编程技巧。 【描述】中的“中国余数定理”是一项重要的数论概念,它在处理多个同余方程组的问题时具有高效的方法。中国余数...
【标签】"HOJ题目"标识了这些文件与HOJ平台的编程题目相关,这可能是历次比赛、练习或挑战赛中的问题,涵盖了各种算法和编程知识领域,例如数据结构、图论、动态规划、排序算法等。 【压缩包子文件的文件名称列表】...
"hoj2055"可能是该系统中一个具体的题目编号,"oj"是Online Judge的缩写,代表在线判题系统,而"绘图软件"可能是指在某些题目中需要使用的图形绘制功能,比如在几何问题或者可视化算法中。 【压缩包子文件的文件...
【hoj小部分题】是针对HOJ...通过解决HOJ中的这些问题,不仅可以提高编程技能,还能为参加其他编程竞赛或面试做好准备。在实际编程过程中,注意代码的可读性和效率,同时利用好调试工具,以便于找出并修复潜在的错误。
【标题】"HOJ_1003_Java"指的是在Hit Online Judge(简称HOJ)平台上的一道编程题目,其对应的解决方案是用Java语言编写的。这道题目可能涉及了算法、数据结构或者特定的编程概念,是检验和提升编程能力的一个实践...
总的来说,"HOJ_1001_Java"是一个适合初学者练习基础编程和算法的题目,通过解决这类问题,可以逐步提升编程技能和算法思维。在HOJ平台上,还可以找到更多不同难度级别的题目,以适应不同层次的学习需求。
【标题】"hoj离线题库最新更新"所涉及的知识点主要集中在计算机科学与技术领域,特别是在线编程竞赛(Online Judge,简称OJ)的相关知识。hoj是众多在线编程竞赛平台之一,它提供了丰富的编程题目供用户进行训练和...
每个子文件可能分别对应一个具体的HOJ题目,详细解释了如何解决该问题。 通过学习这些解题报告,你可以: 1. **掌握算法**:了解并实践各种经典的排序、搜索、图论、动态规划等算法。 2. **提高编程技巧**:学习...
这些题目来自不同的问题集,覆盖了多个方面,如序列处理、游戏策略、路径寻找等。接下来,我们将详细探讨几个具体的例子及其背后的动态规划思想。 ### 题目分析 #### 1. 1031 Piggy-Bank **描述:** 此题目要求...
标题中的"hoj.rar_hoj杭州"表明这是一个与杭州电子科技大学的在线判题系统(Online Judge,简称OJ)相关的压缩文件,其中包含了参赛者或学习者提交的代码。"hoj"通常指的是"杭电OJ",一个用于编程竞赛和训练的平台。...
acm简单题集,适合初学者交流,400道简单题
注意数据范围,所以要用long long
哈工大hoj1037,详细的源代码,附有注释,可以看懂。
c在线题库,希望大家下载 kjbjbk lnknn 你看了可能地方辅导书幅度不断说
GRUB_CMDLINE_LINUX="cgroup_enable=memory swapaccount=1"然后运行以下命令: update-grub && reboot在Node.js项目中安装要求:纱线yarn add hoj-judger自己建造要求:CMake 3.4或更高版本,g ++ 9或更高版本./...
在【标签】"hit-acm-hoj-answer 算法_课件 课件_"中,我们可以推测,这些资源可能包含了HIT ACM HOJ平台上的一些问题的答案,这不仅可以作为学习者的参考,也可以帮助他们在遇到困难时找到解题思路。"算法_课件"和...
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
01背包问题 #include #include #include #include #include using namespace std; int f[2700]; int w[600]; int val[600]; int main() { freopen("in","r",stdin); int t,tt,n,a,b; scanf("%d", &t); ...
采用暴力的思想,搜索所有可能路径。 int matrix[7][7]; int n; void inttoseries(int i,int *s) //将数i化为n进制的n位数 {int k,j; for(k=0,j=i;k;++k) {s[k]=j%n;j/=n;} } int maxcolumn(int *s)//每列最大和 ...
基于SpringCloud与Vue前后端分离,分布式架构的在线测评平台OJ (An open source online judge system base on SpringBoot, Springcloud Alibaba and Vue.js !)