题意：
给定一个无向图，求最少去掉多少个点后使得原图不连通（即存在两点不连通）。
题解：
暴力枚举起点终点，做最小割~取最小的即可
特判一些极端情况，比如m=0等等~
连通度总结（复习用~，转自 ： ）：
图的连通度问题是指：在图中删去部分元素（点或边），使得图中指定的两个点s和t不连通
（不存在从s到t的路径），求至少要删去几个元素。 图的连通度分为点连通度和边连通度： （1）点连通度：只许删点，求至少要删掉几个点（当然，s和t不能删去，这里保证原图中至少有三个点）； （2）边连通度：只许删边，求至少要删掉几条边。 并且，有向图和无向图的连通度求法不同，因此还要分开考虑（对于混合图，只需将其中所有的无向边按照 无向图的办法处理、有向边按照有向图的办法处理即可）。 【1】有向图的边连通度： 这个其实就是最小割问题。以s为源点，t为汇点建立网络，原图中的每条边在网络中仍存在，容量为1， 求该网络的最小割（也就是最大流）的值即为原图的边连通度。 【2】有向图的点连通度： 需要拆点。建立一个网络，原图中的每个点i在网络中拆成i'与i''，有一条边<i', i''>，容量为1 （<s', s''>和<t', t''>例外，容量为正无穷）。原图中的每条边<i, j>在网络中为边<i'', j'>， 容量为正无穷。以s'为源点、t''为汇点求最大流，最大流的值即为原图的点连通度。 说明：最大流对应的是最小割。显然，容量为正无穷的边不可能通过最小割，也就是原图中的边和s、t两个点 不能删去；若边<i, i''>通过最小割，则表示将原图中的点i删去。 【3】无向图的边连通度： 将图中的每条边(i, j)拆成<i, j>和<j, i>两条边，再按照有向图的办法（【1】）处理； 【4】无向图的点连通度： 将图中的每条边(i, j)拆成<i, j>和<j, i>两条边，再按照有向图的办法（【2】）处理。
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 #define N 500 8 #define M 50000 9 #define INF 1e9 10 11 using namespace std; 12 //必须暴力枚举起点和终点，因为 固定的起点可能就是割点 13 int head[N],to[M],next[M],len[M]; 14 int q[M*4],layer[N]; 15 bool map[N][N]; 16 int n,m,S,T,cnt,sn; 17 18 inline void add(int u,int v,int w) 19 { 20 to[cnt]=v; len[cnt]=w; next[cnt]=head[u]; head[u]=cnt++; 21 to[cnt]=u; len[cnt]=0; next[cnt]=head[v]; head[v]=cnt++; 22 } 23 24 inline void read() 25 { 26 memset(map,0,sizeof map); 27 sn=n<<1; 28 int a,b; 29 while(m--) 30 { 31 scanf(" (%d,%d)",&a,&b); 32 a++,b++; 33 map[a][b]=map[b][a]=true; 34 } 35 } 36 37 inline void build() 38 { 39 memset(head,-1,sizeof head); cnt=0; 40 for(int i=1;i<=n;i++) 41 for(int j=1;j<=n;j++) 42 if(map[i][j]) add(i,j+n,INF); 43 for(int i=1;i<=n;i++) 44 { 45 if(i==S||i==T) add(i,i+n,INF),add(i+n,i,INF); 46 else add(i,i+n,1),add(i+n,i,1); 47 } 48 } 49 50 inline bool bfs() 51 { 52 memset(layer,-1,sizeof layer); 53 int h=1,t=2,sta; 54 q[1]=S; layer[S]=0; 55 while(h