题目大意：
给出一个无向图，求解至少删去多少个点，才能使网络不连通。
思路：
就是求割点集中点的数量。利用网络流求解，以任意一点为源点，遍历汇点，最大流的最小值即是需要删去的点的个数。但是需要额外注意三个地方：
需要拆点，将每个点拆成两个相互之间通路容量为1的点。不同点之间建立的通路的容量则为无限。
由于源点可能是割点集中的点，这样计算出的结果可能会大于实际，所以源点也要遍历。
再就是输入样例用第三个例子，这算是特殊情况。整个网络就是一个割点集时，源点汇点无论如何取，结果都会比实际值大。这样的情况也有比较明显的特征，即是最大流的最小值会大于INF，换句话说，网络中的各点都是两两相连的。这时，直接输出节点数即可。
代码：
#include
using namespace std;
#define DATASIZE 50*2
#define INF 1000
int map[DATASIZE+1][DATASIZE+1],backup_map[DATASIZE+1][DATASIZE+1],f[DATASIZE+1],pre[DATASIZE+1],queue[DATASIZE],start,end,n,m;
//n表示边的个数,m表示点的个数,map表示残留网络，f[i]表示处于i点时的最大剩余容量。
int bfs()
{
memset(pre,0,sizeof(pre));
memset(queue,0,sizeof(queue));
int now=0,tail=0;
f[start]=INF;
queue[tail++]=start;
while(tail-now)
{
int head=queue[now++];
if(head==end)
return f[end];
for(int i=1;i<=m*2;i++)
//由于拆点操作，节点个数翻倍。
if(!pre[i]&&map[head][i])
{
f[i]=f[head]<map[head][i]?f[head]:map[head][i];
queue[tail++]=i;
pre[i]=head;
}
}
return -1;
}
int Edmonds_karp()
{
int temp_flow,max_flow=0;
while((temp_flow=bfs())!=-1)
{
max_flow+=temp_flow;
for(int i=end;i!=start;i=pre[i])
{
map[pre[i]][i]-=temp_flow;
map[i][pre[i]]+=temp_flow;
}
}
return max_flow;
}
int solved(int s,int e)
//计算s为源点，e为汇点的最大流。
{
start=s;
end=e;
//start和end为计算最大流的接口，非别表示源点和汇点。
for(int i=1;i<=m*2;i++)
for(int j=1;j<=m*2;j++)
//每次计算前都要初始化残留网络
map[i][j]=backup_map[i][j];
return Edmonds_karp();
//初始化完start和end以及残留网络map之后，就可以调用Edmonds_karp()，其返回值为最大流。
}
void add_edge(int u,int v)
//在节点u、v之间建立通路。
{
backup_map[v][v+m]=1;
backup_map[u][u+m]=1;
//拆点操作，将u（v）拆成u（v）和u+m（v+m）两个点，之间通路的容量为1。
backup_map[u+m][v]=INF;
backup_map[v+m][u]=INF;
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
if(m<=1)
{
printf("%d\n",m);
continue;
}
if(n==0)
{
printf("0\n");
continue;
}
memset(backup_map,0,sizeof(backup_map));
for(int i=0,u,v;i<n;i++)
{
scanf(" (%d,%d)",&u,&v);
add_edge(u+1,v+1);
}
int min=INF;
for(int i=1;i<=m;i++)
for(int j=i+1;j<=m;j++)
//由于是无向图，源点汇点交换位置不影响最大流的值，所以j从i+1开始。
{
int res=solved(i+m,j);
min=min=INF?m:min);
//输出时判断下min与INF是否相等，目的是判断当前是否处于整个网络就是一个割点集这种特殊情况。
}
}
后记：
提交后时间为250ms，由于是EK是O(VE^2)的复杂度，相比较SAP的O(EV^2)有不小的差距。曾设想进行优化，由于每次求最大流都要两层循环backup_map[][]初始化残留网络map[][]，于是就想从矩阵复制入手。
思考了会，想起了memcpy，它可以进行连续空间的复制，但由于数组只有一维度上是连续的，所以还是免不了外层循环。满怀期待的尝试，结果却令人大跌眼镜，782ms！这货比for循环还慢，跟它兄弟memset差太多了。
之前看过NotOnlySuccess的《网络流的几个常见算法》，结论上说基本没题会去卡SAP，而却EK很悲剧，看来又得重新写模板了。
下面是用《网络流的几个常见算法》里的“sap+gap优化”模板写的代码，时间从250ms降到了141ms，非常可观的优化。美中不足的是这模板毕竟属于别人，风格上差别太大。虽然代码短小，但是使用了goto无疑是种缺憾。想手动改成递归，效率低些不要紧，但发现无从下手，我对sap的理解还太嫩，不会改啊。
#include
using namespace std;
#define MAXN 50*2
#define INF MAXN+1
int map[MAXN][MAXN],backup_map[MAXN][MAXN];
int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];
//非负整数dis[i]描述i点到汇点的最少弧的数量，初始化均为0。
int m,n;
int sap(int s,int t,int total)
//s源点，t汇点，total节点的个数
{
memset(cur,0,sizeof(cur));
memset(dis,0,sizeof(dis));
memset(gap,0,sizeof(gap));
int u=pre[s]=s,maxflow=0,aug=-1;
gap[0]=total;
while(dis[s]<total)
{
loop:
for(int v=cur[u];vmap[u][v])
aug=map[u][v];
pre[v]=u;
u=cur[u]=v;
if(v==t)
{
maxflow+=aug;
for(u=pre[u];v!=s;v=u,u=pre[u])
{
map[u][v]-=aug;
map[v][u]+=aug;
}
aug=-1;
}
goto loop;
}
int mindis=total-1;
for(int v=0;vdis[v])
{
cur[u]=v;
mindis=dis[v];
}
if(!(--gap[dis[u]]))
break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return maxflow;
}
int solved(int s,int e)
//计算s为源点，e为汇点的最大流。
{
for(int i=0;i<m*2;i++)
for(int j=0;j<m*2;j++)
//每次计算前都要初始化残留网络
map[i][j]=backup_map[i][j];
return sap(s,e,2*m);
//初始化完start和end以及残留网络map之后，就可以调用sap()，其返回值为最大流。
}
void add_edge(int u,int v)
//在节点u、v之间建立通路。
{
backup_map[v][v+m]=1;
backup_map[u][u+m]=1;
//拆点操作，将u（v）拆成u（v）和u+m（v+m）两个点，之间通路的容量为1。
backup_map[u+m][v]=INF;
backup_map[v+m][u]=INF;
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
if(m<=1)
{
printf("%d\n",m);
continue;
}
if(n==0)
{
printf("0\n");
continue;
}
memset(backup_map,0,sizeof(backup_map));
for(int i=0,u,v;i<n;i++)
{
scanf(" (%d,%d)",&u,&v);
add_edge(u,v);
}
int min=INF;
for(int i=0;i<m;i++)
for(int j=i+1;j<m;j++)
//由于是无向图，源点汇点交换位置不影响最大流的值，所以j从i+1开始。
{
int res=solved(i+m,j);
min=min=INF?m:min);
//输出时判断下min与INF是否相等，目的是判断当前是否处于整个网络就是一个割点集这种特殊情况。
}
}