题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2182
题意:给出一个无向图,问最少删掉多少个顶点之后图变得不连通?
思路:将原图每个点拆点(i,i+n),连边<i,i+n,1>,对原图的边(u,v),连边<u+n,v,INF>,<v+n,u,INF>。然后对于每对顶点(i,j)跑最大流(i+n,j)。所有最大流的最小值即为答案。
struct node { int v,cap,next; }; node edges[N*10]; int head[N],e; int curedge[N],h[N],num[N],pre[N]; int s,t; void add(int u,int v,int cap) { edges[e].v=v; edges[e].cap=cap; edges[e].next=head[u]; head[u]=e++; } void Add(int u,int v,int cap) { add(u,v,cap); add(v,u,0); } int Maxflow(int s,int t,int n) { clr(h,0); clr(num,0); int i; FOR0(i,n+1) curedge[i]=head[i]; int u=s,Min,k,x,ans=0; while(h[u]<n) { if(u==t) { Min=INF*100; for(i=s;i!=t;i=edges[curedge[i]].v) { x=curedge[i]; if(edges[x].cap<Min) { Min=edges[x].cap; k=i; } } ans+=Min; u=k; for(i=s;i!=t;i=edges[curedge[i]].v) { x=curedge[i]; edges[x].cap-=Min; edges[x^1].cap+=Min; } } for(i=curedge[u];i!=-1;i=edges[i].next) { if(edges[i].cap>0&&h[u]==h[edges[i].v]+1) { break; } } if(i!=-1) { curedge[u]=i; pre[edges[i].v]=u; u=edges[i].v; } else { if(--num[h[u]]==0) break; curedge[u]=head[u]; x=n; for(i=head[u];i!=-1;i=edges[i].next) { k=edges[i].v; if(edges[i].cap>0&&h[k]<x) x=h[k]; } h[u]=x+1; num[x+1]++; if(u!=s) u=pre[u]; } } return ans; } int n,m; int a[55][55]; int visit[55]; void DFS(int u) { visit[u]=1; int i,v; FOR1(i,n) if(a[u][i]&&!visit[i]) { DFS(i); } } int ok() { clr(visit,0); DFS(1); int i; FOR1(i,n) if(!visit[i]) return 0; return 1; } int cal(int s,int t) { clr(head,-1); e=0; int i,j; FOR1(i,n) Add(i,i+n,1); FOR1(i,n) for(j=1;j<=n;j++) if(a[i][j]) { Add(i+n,j,INF); } return Maxflow(s+n,t,n+n+2); } int get() { int x=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } return x; } int main() { while(scanf("%d%d",&n,&m)!=-1) { if(m==0) { if(n==0) puts("0"); else if(n==1) puts("1"); else puts("0"); continue; } clr(a,0); int u,v,i; FOR0(i,m) { u=get(); v=get(); a[u+1][v+1]=a[v+1][u+1]=1; } if(!ok()) { puts("0"); continue; } int j; int ans=INF; FOR1(i,n) for(j=1;j<=n;j++) if(i!=j) { int x=cal(i,j); ans=min(ans,x); } if(ans==INF||ans==n-1) ans=n; PR(ans); } }
ZOJ 2182 Cable TV Network(无向图点割-最大流)的更多相关文章
-
POJ 1966 ZOJ 2182 Cable TV Network
无向图顶点连通度的求解,即最少删除多少个点使无向图不连通. 我校“荣誉”出品的<图论算法理论.实现及其应用>这本书上写的有错误,请不要看了,正确的是这样的: 对于每个顶点,分成两个点,v和 ...
-
poj1966Cable TV Network——无向图最小割(最大流)
题目:http://poj.org/problem?id=1966 把一个点拆成入点和出点,之间连一条边权为1的边,跑最大流即最小割: 原始的边权赋成inf防割: 枚举源点和汇点,直接相邻的两个点不必 ...
-
Cable TV Network 顶点连通度 (最大流算法)
Cable TV Network 题目抽象:给出含有n个点顶点的无向图,给出m条边.求定点联通度 K 算法:将每个顶点v拆成 v' v'' ,v'-->v''的容量为1. ...
-
POJ 1966 Cable TV Network (无向图点连通度)
[题意]给出一个由n个点,m条边组成的无向图.求最少去掉多少点才能使得图中存在两点,它们之间不连通. [思路]回想一下s->t的最小点割,就是去掉多少个点能使得s.t不连通.那么求点连通度就枚举 ...
-
UVA-1660 Cable TV Network (最小割)
题目大意:给一张n个点.m条边的无向图,求最小点割集的基数. 题目分析:求无向图最小点割集的基数可以变成求最小割.考虑单源s单汇t的无向图,如果要求一个最小点集,使得去掉这个点集后图不再连通(连通分量 ...
-
POJ 1966 Cable TV Network (最大流最小割)
$ POJ~1966~Cable~TV~Network $ $ solution: $ 第一眼可能让人很难下手,但本就是冲着网络流来的,所以我们直接一点.这道题我们要让这个联通图断开,那么势必会有两个 ...
-
POJ 1966 Cable TV Network(顶点连通度的求解)
Cable TV Network Time Limit: 1000MS Memory Limit: 30000K Total Submissi ...
-
UVA1660 电视网络 Cable TV Network
题目地址:UVA1660 电视网络 Cable TV Network 枚举两个不直接连通的点 \(S\) 和 \(T\) ,求在剩余的 \(n-2\) 个节点中最少去掉多少个可以使 \(S\) 和 \ ...
-
POJ 1966 Cable TV Network
Cable TV Network Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 4702 Accepted: 2173 ...
随机推荐
-
[转]Android应用程序框架思路整理
一.一般Android应用程序架构(Book,购彩,Market). 普通的应用程序由于只需要用到Android的联网与显示的功能,所以应用程序大体上是呈现为UI(Activities)与网络(Net ...
-
.net 使用validator做数据校验
概述 在把用户输入的数据存储到数据库之前一般都要对数据做服务端校验,于是想到了.net自带的数据校验框架validator.本文对validator的使用方法进行介绍,并分析下校验的的原理. 使用va ...
-
dump json 显示中文问题
[root@dr-mysql01 ~]# cat a2.pl my $url="http://192.168.32.101:3000/api/getcode?env=zj&phone ...
-
Java开发规范总结
Service / DAO 层方法命名规约: 1 ) 获取单个对象的方法用 get 做前缀.2 ) 获取多个对象的方法用 list 做前缀.3 ) 获取统计值的方法用 count 做前缀.4 ) 插 ...
-
django rest framework 与 Vue 整合遇到的坑
前提是已经有了Django项目与前端Vue打包好的dist文件 好,开始整合!!! 当然还是先设置Django的setting.py 1设置模板路径 2 设置静态文件路径 TEMPLATES = [ ...
-
POJ - 2096 Collecting Bugs(概率dp)
https://vjudge.net/problem/POJ-2096 题意 一个软件有s个子系统,会产生n种bug.某人一天发现一个bug,这个bug属于某种bug,发生在某个子系统中.求找到所有的 ...
-
HDU 6390 GuGuFishtion
题意: 计算: \[\sum\limits_{a = 1}^{m}\sum\limits_{b = 1}^{n} \frac{\varphi(ab)}{\varphi(a)\varphi(b)} (\ ...
-
sourcetree基本使用
非常有用的使用sourcetree开发的步骤文档 https://www.cnblogs.com/fps2tao/p/7825742.html 1) master,最终发布版本,整个项目中有且只有一个 ...
-
freemarker特殊字符输出
期望输出: #{fefefefwewrerwerwrrrre}${fffqqqwwwwwwwwwwwwwwww} 但是以上解析ftl时候会报错!!!!!!!!!!!! 解决办法: 方法1:使用${r& ...
-
webview 播放H5视频问题 黑屏 只有声音没有画面
android 用webview 播放网络视频怎控制播放按键? 在代码中加入webview.getSettings().setJavaScriptEnabled(true);//支持jswebview ...