枚举源汇最小割
#include#include #include #include 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\n",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\n",ans); } return 0;}