POJ1966.CableTVNetwork——无向图的点连通度

作者:网络    软件教程库   2020-05-21

http://poj.org/problemid=1966

题目描述:
有线电视网络中,中继器的连接是双向的。如果网络中任何两个中继器之间至少有一条路,则中继器网络称为是连通的,否则中继器网络是不连通的。一个空的网络、以及只有一个中继器的网络被认为是连通的。具有n 个中继器的网络的安全系数f 被定义成:
(1) f 为n,如果不管删除多少个中继器,剩下的网络仍然是连通的;
(2) f 为删除最少的顶点数,使得剩下的网络不连通。

分析:
本题中的安全系数f 实际上就是无向图的顶点连通度κ(g)。

拆点建边 cap(u,u’)=1
(u,v)- cap(u’,v)=inf,cap(v’,u)=inf

固定一个源点,枚举汇点,多次求解最大流
当maxflow=0,说明source与sink不连通
当maxflow=inf,说明source与sink相邻
否则,maxflow=p(source,sink) ,p(u,v)为独立轨的数目

//248k  16ms    c++
#include iostream
#include cstring
#include cstdio
#include algorithm
#include cstdlib
#define rep(i,n) for(int i=0;i(n);++i)
#define rep1(i,a,b) for(int i=(a);i(b);++i)
#define clr(a,b) memset(a,b,sizeof(a))
#define min(a,b) (aba:b)
const int maxn = 110;
const int maxm = 10010;
const int inf = 0x3f3f3f3f;
using namespace std;

int maze[maxn][maxn];
int gap[maxn],dis[maxn],pre[maxn],cur[maxn];
int flow[maxn][maxn];
int sap(int source,int sink,int n){
    clr(cur,0);
    clr(dis,0);
    clr(gap,0);
    clr(flow,0);
    int u=pre[source]=source,maxflow=0,aug=-1;
    gap[0]=n;
    while(dis[source]n){
        int ok=0;
        for(int v=cur[u];vn;++v){
            if(maze[u][v]-flow[u][v]dis[u]==dis[v]+1){
                if(aug==-1||augmaze[u][v]-flow[u][v])
                    aug=maze[u][v]-flow[u][v];
                pre[v]=u;
                u=cur[u]=v;
                ok=1;
                if(v==sink){
                    maxflow+=aug;
                    for(u=pre[u];v!=source;v=u,u=pre[u]){
                        flow[u][v]+=aug;
                        flow[v][u]-=aug;
                    }
                    aug=-1;
                }
                break;
            }
        }
        if(ok) continue;
        int mindis=n-1;
        for(int v=0;vn;++v){
            if(maze[u][v]-flow[u][v]mindisdis[v]){
                cur[u]=v;
                mindis=dis[v];
            }
        }
        if((--gap[dis[u]])==0) break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return maxflow;
}
int main()
{
#ifndef online_judge
freopen("in.cpp","r",stdin);
#endif // online_judge
    int n,m,u,v;
    while(scanf("%d%d",n,m)==2){
        clr(maze,0);
        rep(i,n) maze[i][i+n]=1;
        rep(i,m){
            scanf(" (%d,%d)",u,v);
            maze[u+n][v]=inf;
            maze[v+n][u]=inf;
        }
        int ans=inf;
        rep1(i,1,n){
            int tmp=sap(0+n,i,n1);
            ans=min(ans,tmp);
        }
        if(ans==inf) printf("%d\n",n);
        else printf("%d\n",ans);
    }
    return 0;
}

poj1966.cable tv network——无向图的点连通度

原文地址:http://blog.csdn.net/u014141559/article/details/45422275

这篇内容就是由软件教程库 小编为各位整理 原文链接:https://www.itjcku.com/9999/1091534.html

阅读全部内容


Tags:

返回首页



推荐内容

Oracle备忘录1

数据库管理员:安装升级oracle数据库建库,表空间,表,视图,索引。。。制定并实施备份和修复计划数据库权限管理,调优, ...

FileStream文件流

使用文件流拷贝一个较大的多媒体文件: public static void copyfile(string soucr ...

C语言BFS(5)___TT与魔法师(swustoj2464)

description tt生活在一个充满魔法的国度,为了便于管理,国王请魔法师在一些重要的城市之间造出 ...

进程类Process与多线程Thread

进程类(process)的基本操作: //通过进程类查询系统所有进程 process[] pr ...

Xml解析方式之Pull解析器的使用

xml有多种解析的方式,这篇文章只介绍用pull解析器来解析xml文件,接下来我会说明使用pull解析器来读取xml文件 ...

enum,EnumMap,EnumSet

enum基本使用 : package com.enumtest; enum shrubbery { gr ...

Hibernate乱码问题解决

乱码问题其实归根接地就是两端的字符集不统一。 解决思路也有两种: 1. 修改两端字符集统一。 2. 通过代码进行转 ...

eclipse集成struts2.3.20

需要强调的是,这里介绍的是在eclipse工具下集成struts2.3.20而不是myeclipse添加对struts2 ...

ubi文件系统制作,还是"-c"选项的问题

以下是分析记录: --------------------------------------------------- ...

如何把事情做到最好读书笔记1

开篇语: 每个人生来都具备足够的潜力,每个人都能做到别人#30524;中难以企及的事情。请永远保持初学之心,勇敢面对 ...

如何把事情做到最好读书笔记2

第二章 认清自己:你属于哪种类型的人 你必须足够了解你自己,下面有三种类型的人、 (1)浅尝辄止者 浅尝辄止者对一切 ...

如何把事情做到最好读书笔记3

第三章 一份耕耘才能一份收获 当你决定踏上精益求精之路时,你会突然发现周围的一切都与你所追求的#26684;#2668 ...

如何把事情做到最好读书笔记4

第四章 热爱平台期 从小,我们接受的教育就是好好学习,这样才能上好的大学,上好的大学才能找到好工作,有好工作才能有钱买 ...

习题10-21二项式系数UVa1649

1.题目描述:点击打开链接 2.解题思路:本题利用枚举#43;二分解决。问题的关键是选对枚举对象,因为要找c(n,k)= ...

mysql小技巧

selectnow(),user(),version(),database(); #最后输入\c是放弃的意思 des ...

Java学习笔记——面试常客:写出一个死锁的例子

现在的面试挺蛋疼,为了考察大家的语言掌握水平,类#20284;这样的题特别多,不过在某个角度来说确实能看出一个人对某个知 ...

UVA-10396VampireNumbers暴力+打表

题目大意:给出n,要求你输出所有符合规则的n位数 规则如下,这个n位数由两个n/2位数相乘得到,并且满足 1.这n位 ...

CF148D.Bagofmice[概率dp]

题目链接:http://codeforces.com/problemset/problem/148/d 题目大意:一袋子 ...

HDU-1846-BraveGame(巴什博弈)

题目传送:brave game 介绍: 巴什博奕(bash game): 首先我们来玩一个比较古老的报数游戏。a ...

HDU-2149-PublicSale(巴什博弈)

题目传送:public sale 思路:巴什博弈 ac代码: #include lt;cstdiogt; # ...

enum实现售卖机

首先 推荐一下google的代码风格 :https://google-styleguide.googlecode ...

批量添加用户

a、创建用户文件,因为添加的用户比较多,因此编写脚本创建一个用户文件user.txt #!/bin/ba ...

解决侧滑中ViewPager和SlidingMenu的滑动冲突

当我们在使用开源框架slidingmenu时,如果要是使用到viewpager,就会出现滑动冲突。 解决方案: }/** ...

shell打乱文件行

思路,产生一个随机数组,然后按按照数组的元素将文件中行的重新输出 1、随机数组的生成 看书的时候感觉很是简单。第 ...

编程之美2015初赛第二场AB

题目1 : 扑克牌 时间限制:2000ms 单点时限:1000ms 内存限制:256mb 描述 一副不含王的扑 ...

Java设计模式之单例模式(恶汉式和懒汉式)

/* * 单例模式: * 饿汉式:类一加载就创建对象 * 懒汉式:用的时候,才去创建对象 * 面试题:单例模式的 ...

Html简单介绍

1、html--- hypertext markup language 的缩写 --- 超文本 标记 语言. 这个技 ...

configure:error:youmustconfigureinaseparatebuilddirectory

configure glibc-2.14 时出现以下错误: [[email#160;protected] opt]# ...

kohana框架生成feed

创建feed feed::create()斱法用给定癿参数杢创建 rss戒者 atom feed。下面是可接叐癿参数。 ...

用USB安装linux

手边没有光驱,安装ubuntu可以用 linuxlive usb creator 2.9.3,在百度网盘里有的。http ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com