`
Coco_young
  • 浏览: 125332 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

[割点问题]HOJ 12307 Disconnected Pair

 
阅读更多

传送门: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题目备份,值得拥有

    【标签】"HOJ题目"标识了这些文件与HOJ平台的编程题目相关,这可能是历次比赛、练习或挑战赛中的问题,涵盖了各种算法和编程知识领域,例如数据结构、图论、动态规划、排序算法等。 【压缩包子文件的文件名称列表】...

    HOJ.rar_HOJ_hoj2055_oj_绘图软件

    "hoj2055"可能是该系统中一个具体的题目编号,"oj"是Online Judge的缩写,代表在线判题系统,而"绘图软件"可能是指在某些题目中需要使用的图形绘制功能,比如在几何问题或者可视化算法中。 【压缩包子文件的文件...

    hoj小部分题

    【hoj小部分题】是针对HOJ...通过解决HOJ中的这些问题,不仅可以提高编程技能,还能为参加其他编程竞赛或面试做好准备。在实际编程过程中,注意代码的可读性和效率,同时利用好调试工具,以便于找出并修复潜在的错误。

    HOJ_1003_Java

    【标题】"HOJ_1003_Java"指的是在Hit Online Judge(简称HOJ)平台上的一道编程题目,其对应的解决方案是用Java语言编写的。这道题目可能涉及了算法、数据结构或者特定的编程概念,是检验和提升编程能力的一个实践...

    HOJ_1001_Java

    总的来说,"HOJ_1001_Java"是一个适合初学者练习基础编程和算法的题目,通过解决这类问题,可以逐步提升编程技能和算法思维。在HOJ平台上,还可以找到更多不同难度级别的题目,以适应不同层次的学习需求。

    hoj 离线题库 最新更新

    【标题】"hoj离线题库最新更新"所涉及的知识点主要集中在计算机科学与技术领域,特别是在线编程竞赛(Online Judge,简称OJ)的相关知识。hoj是众多在线编程竞赛平台之一,它提供了丰富的编程题目供用户进行训练和...

    hoj.rar_HOJ

    每个子文件可能分别对应一个具体的HOJ题目,详细解释了如何解决该问题。 通过学习这些解题报告,你可以: 1. **掌握算法**:了解并实践各种经典的排序、搜索、图论、动态规划等算法。 2. **提高编程技巧**:学习...

    HOj DP 分类 Zhouguyue

    这些题目来自不同的问题集,覆盖了多个方面,如序列处理、游戏策略、路径寻找等。接下来,我们将详细探讨几个具体的例子及其背后的动态规划思想。 ### 题目分析 #### 1. 1031 Piggy-Bank **描述:** 此题目要求...

    hoj.rar_hoj杭州

    标题中的"hoj.rar_hoj杭州"表明这是一个与杭州电子科技大学的在线判题系统(Online Judge,简称OJ)相关的压缩文件,其中包含了参赛者或学习者提交的代码。"hoj"通常指的是"杭电OJ",一个用于编程竞赛和训练的平台。...

    HOJ简单题400道源码

    acm简单题集,适合初学者交流,400道简单题

    HOJ1002:A+B+C

    注意数据范围,所以要用long long

    哈工大hoj1037

    哈工大hoj1037,详细的源代码,附有注释,可以看懂。

    c在线题库(hoj)

    c在线题库,希望大家下载 kjbjbk lnknn 你看了可能地方辅导书幅度不断说

    hoj-judger:HydrogenOJ的简单沙箱和判断器

    GRUB_CMDLINE_LINUX="cgroup_enable=memory swapaccount=1"然后运行以下命令: update-grub && reboot在Node.js项目中安装要求:纱线yarn add hoj-judger自己建造要求:CMake 3.4或更高版本,g ++ 9或更高版本./...

    hit.rar_HIT-acm-HOJ-answer_算法 课件_课件

    在【标签】"hit-acm-hoj-answer 算法_课件 课件_"中,我们可以推测,这些资源可能包含了HIT ACM HOJ平台上的一些问题的答案,这不仅可以作为学习者的参考,也可以帮助他们在遇到困难时找到解题思路。"算法_课件"和...

    动态规划背包问题入门

    动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496

    hoj2196 01背包.cpp

    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); ...

    HOJ matrix 源代码

    采用暴力的思想,搜索所有可能路径。 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)//每列最大和 ...

    hoj-master.zip

    基于SpringCloud与Vue前后端分离,分布式架构的在线测评平台OJ (An open source online judge system base on SpringBoot, Springcloud Alibaba and Vue.js !)

Global site tag (gtag.js) - Google Analytics