最近写的代码都挺长的啊...
下面说一下最小割吧。
以下内容引自：这里
首先介绍一个概念：
点连通度：一个具有N个顶点的图G，去除K个顶点后，图成为非连通图，去除任意K-1个顶点后，图仍为连通图。责成图G为K连通图。
独立轨：A,B是图G中两个顶点，从A至B的无公共内顶点的路径叫做独立轨，其最大条数记为p(A,B);
如上图中，将A=1,B=5;那么该图的最大独立轨数量为3
1-2-3-5,1-4-5,1-7-6-5;三条。
在这三条独立轨中，每条切除一个内点，该图的成为非连通图。如果p（G）=N-1，则该图为强连通图。
可见p(A,B)=K(G)。也就是图G独立轨的最大条数为图G的连通度。
由于每个内点只能用一次，可以套最大流模型...
将顶点v分割为v,v',e=(v,v')容量为1；做一次最大流就可以得出源点到汇点的最小割。
G无向图：
（1）顶点v分割为v，v'。e(v,v')容量为1;
（2）图中的无向边设为2条有向边,e(u,v)-->e(u',v)=INF,e(v',u)=INF;
（3）枚举源点u'和汇点v做最大流。
G有向图类似。
若结果流出的值为INF，则该图为强连通，去除N个顶点才能破坏连通性。
所有具有流量为1的弧（V,V'）对应的V顶点组成一个割顶集
通过求连通度可以得到一个结论：G是K的连通图，k>=2,则任意K个顶点共圈。
边连通度：
解法类似，不过边连通，点可以走很多次，边只能走一次。
（1）对于无向边e(u,v) 在(u,v),(v,u)之间添加容量为1的流边。
（2）枚举源点汇点，求最大流，即为边连通度。
求出的残余网络中，流量为1的弧e`=(u,v),则e`就是割边。
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define MN 111
#define INF 0x3FFFFFFF
#define CC(a) memset( a,0,sizeof(a) )
#define FF(i,N) for( int i=0;i<N;i++ )
template<class T>void inline checkmin( T &a,T b ){ if( a>b||a==-1 ) a=b; }
template<class T>void inline checkmax( T &a,T b ){ if( a<b ) a=b; }
using namespace std;
int maze[MN][MN],map[MN][MN],dis[MN],cur[MN],gap[MN],pre[MN];
int N,M,s,t;
void setG()
{
CC(map);
FF( i,N )
map[i][i+N]=1;
int u,v;
FF( i,M ){
scanf( " (%d,%d)",&u,&v );
map[u+N][v]=map[v+N][u]=INF;
}
}
void initG()
{
FF(i,N<<1)FF(j,N<<1)
maze[i][j]=map[i][j];
}
int sap( int s,int t )
{
CC(cur),CC(gap),CC(dis);
int u=pre[s]=s,maxflow=0,aug=-1;
gap[0]=2*N;
while( dis[s]<2*N ){
loop:
for( int v=cur[u];v<2*N;v++ )
if( maze[u][v]&&dis[u]==dis[v]+1 )
{
pre[v]=u;
cur[u]=v;
checkmin( aug,maze[u][v] );
u=v;
if( v==t )
{
maxflow+=aug;
for( u=pre[u];v!=s;v=u,u=pre[u] )
maze[u][v]-=aug,maze[v][u]+=aug;
aug=-1;
}
goto loop;
}
int mind=2*N;
for( int v=0;v<2*N;v++ )
if( maze[u][v]&&mind>dis[v] )
{
mind=dis[v];
cur[u]=v;
}
if( --gap[dis[u]]==0 ) break;
gap[dis[u]=mind+1]++;
u=pre[u];
}
return maxflow;
}
int main()
{
while( scanf("%d%d",&N,&M)!=EOF )
{
int ans=INF;
setG();
for( int i=0;i<N;i++ )
for( int j=i+1;j<N;j++ )
{
initG();
checkmin( ans,sap(i+N,j) );
//printf( "ans:%d\n",ans );
}
if( ans==INF )
printf( "%d\n",N );
else
printf( "%d\n",ans );
}
return 0;
}