枚举源汇最小割
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N=102; const int M=2002; const int inf=0x3f3f3f3f; struct edge { int to,next,w; }e[M]; int head[N],ecnt=1,cur[N]; int S,T,n,m; int st[M],ed[M]; int dep[N],q[N],qr; inline void add(int u,int v,int w) { e[++ecnt].to=v;e[ecnt].next=head[u];head[u]=ecnt;e[ecnt].w=w; e[++ecnt].to=u;e[ecnt].next=head[v];head[v]=ecnt;e[ecnt].w=0; } bool bfs() { for(int i=1;i<=T;i++) dep[i]=-1,cur[i]=head[i]; q[qr=1]=S;dep[S]=0; for(int ql=1;ql<=qr;ql++) { int u=q[ql]; for(int i=head[u],v;i;i=e[i].next) { if(e[i].w && dep[v=e[i].to]==-1) { dep[v]=dep[u]+1; q[++qr]=v; if(v==T) return 1; } } } return 0; } int dinic(int u,int flow) { if(u==T) return flow; int ret=0,delta,v; for(int &i=cur[u];i;i=e[i].next) { if(e[i].w && dep[v=e[i].to]==dep[u]+1) { delta=dinic(v,min(e[i].w,flow-ret)); if(delta) { e[i].w-=delta; e[i^1].w+=delta; ret+=delta; if(flow==ret) break; } } } if(flow!=ret) dep[u]=-1; return ret; } void build_graph(int x,int y) { ecnt=1; memset(head,0,sizeof(head)); add(S,x,inf);add(y+n,T,inf); for(int i=1;i<=n;i++) { if(i!=x &&i!=y) add(i,i+n,1); else add(i,i+n,inf); } for(int i=1;i<=m;i++) add(st[i]+n,ed[i],inf),add(ed[i]+n,st[i],inf); } int read() { int ret=0,op=1,c=getchar(); while(c<'0' || c>'9') { if(c=='-') op=-1; c=getchar(); } while(c>='0' && c<='9') { ret=ret*10+c-'0'; c=getchar(); } return ret*op; } int main() { while(~scanf("%d%d",&n,&m)) { S=2*n+1;T=S+1; for(int i=1;i<=m;i++) { st[i]=read(); ed[i]=read(); ++st[i],++ed[i]; //printf("%d->%d ",st[i],ed[i]); } int ans=n; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { build_graph(i,j); int maxflow=0; while(bfs()) maxflow+=dinic(S,inf); ans=min(ans,maxflow); } printf("%d ",ans); } return 0; }