题目：http://poj.org/problem?id=1966
把一个点拆成入点和出点，之间连一条边权为1的边，跑最大流即最小割；
原始的边权赋成inf防割；
枚举源点和汇点，直接相邻的两个点不必枚举；
注意：1、源点为枚举点i的出点，汇点为枚举点j的入点；
2、读入方式，免空格；
3、在dinic跑最大流的过程中，会改变边权，因此每次枚举都要复制一组边跑最大流，以免影响后面；
另：数据中的点从0开始，所以读入的时候++来使用。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
queue<int>q;
int n,m,head[],cur[],ct=,inf=1e9,ans,d[];
bool sid[][];
struct N{
int to,next,w;
N(int t=,int n=,int ww=):to(t),next(n),w(ww) {}
}edge[],ed[];
void add(int x,int y,int z)
{
ed[++ct]=N(y,head[x],z);head[x]=ct;
ed[++ct]=N(x,head[y],);head[y]=ct;
}
bool bfs(int s,int t)
{
memset(d,,sizeof d);
while(q.size())q.pop();
d[s]=;q.push(s);
while(q.size())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].next)
{
int u=edge[i].to;
if(!d[u]&&edge[i].w)
{
d[u]=d[x]+;
q.push(u);
}
}
}
return d[t];
}
int dfs(int x,int f,int t)
{
if(x==t)return f;
int res=;
for(int i=cur[x];i;i=edge[i].next)
{
int u=edge[i].to;
if(d[u]==d[x]+&&edge[i].w)
{
int tmp=dfs(u,min(edge[i].w,f-res),t);
edge[i].w-=tmp;
edge[i^].w+=tmp;
res+=tmp;
if(edge[i].w)cur[x]=i;
if(res==f)return f;
}
}
if(!res)d[x]=;
return res;
}
int dinic(int s,int t)
{
memcpy(edge,ed,sizeof ed);//!!!
int res=;
while(bfs(s+n,t))
{
for(int i=;i<=*n;i++)cur[i]=head[i];
res+=dfs(s+n,inf,t);
}
return res;
}
int main()
{
while(scanf("%d%d",&n,&m)==)
{
if(!n||n==)
{
printf("%d\n",n);
continue;
}
if(!m)
{
printf("0\n");
continue;
}
ct=;ans=inf;
memset(head,,sizeof head);
memset(sid,,sizeof sid);
for(int i=;i<=n;i++)add(i,i+n,);
// char dc=0;
for(int i=;i<=m;i++)
{
// dc=0;
// while(dc!='(')scanf("%c",&dc);
int x,y;
scanf(" (%d,%d)",&x,&y);//或者采用注释方法读入，这里为 scanf("%d,%d",&x,&y);
x++;y++;//
sid[x][y]=;sid[y][x]=;
add(x+n,y,inf);
add(y+n,x,inf);
}
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
if(!sid[i][j])ans=min(ans,dinic(i,j));
if(ans==inf)ans=n;
printf("%d\n",ans);
// dc=0;
// while(dc!=')')scanf("%c",&dc);
}
return ;
}