最大流最小割定理
任何一个网络的最大流量等于最小割中边的容量之和 即最大流等于最小割
点边转化
节点可以拆为入点和出点 把点的属性添加到入点和出点之间的边上 图的边也可以分两截 在中间加一个节点 把边的属性体现在入点和出点的 边上。
题目链接
题目大意
给定一张无向图，求最少去掉多少个点可以使图不联通。N<=50。
题目思路
将每个点拆分为 入点和出点 每条边（a，b）改为 （a出，b入）和 （a入，b出）
将这些边的容量标为max
对于每个点 对他拆成的入点和出点画一条边 代表这个点
其中该边容量标为1
因为求的是最小割这样可以使 这些标为max的边永远不会被切割 而只会切割标为1的
这样初始化完之后
每次枚举两个不直接相连的点 作为网络流的S和T 后跑Dinic模板
每次枚举最小的maxflow即为答案
代码
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int maxn=105;
const int M=5e3+10;
const int N=5e3+10;
const int inf=0x3f3f3f3f;
int n,m;
int mp[maxn][maxn];
int maxflow;
int cnt;
int INF=inf;
struct Dinic{//Dinic模板 int s, t;//int tes = 1;int head[N], d[N], now[N];struct Edge{int nxt, to, v,val;} ed[M];queue<int>q;void init(){cnt=1;memset(mp,0,sizeof mp);memset(head,0,sizeof(head));memset(ed,0,sizeof(ed));memset(now,0,sizeof(now));memset(d,0,sizeof(d));}void add(int u, int v, int w){ed[++ cnt] = (Edge){head[u], v, w};head[u] = cnt;ed[++ cnt] = (Edge){head[v], u, 0};head[v] = cnt;}bool bfs(){while(!q.empty()) q.pop();memset(d, 0, sizeof(d));q.push(s); d[s] = 1; now[s] = head[s];while(!q.empty()){int u = q.front(); q.pop();for(int i = head[u]; i; i = ed[i].nxt){int v = ed[i].to, w = ed[i].val;if(!d[v] && w){now[v] = head[v];d[v] = d[u] + 1;if(v == t) return true;q.push(v);}}}return false;}int dinic(int u, int flow){if(u == t) return flow;int rest = flow, i;for(i = now[u]; i && rest; i = ed[i].nxt){int v = ed[i].to, w = ed[i].val;if(w && d[v] == d[u] + 1){int k = dinic(v, min(rest, w));if(!k) d[v] = 0;ed[i].val -= k;ed[i ^ 1].val += k;rest -= k;}}now[u] = i;return flow - rest;}void work(int S, int T){s = S, t = T;int flow = 0;maxflow = 0;while(bfs())while(flow = dinic(s, INF)) maxflow += flow;}
} G;
int main()
{string s;while(cin>>n>>m){G.init();int ans=n;for(int i=1;i<=m;i++){int st;int en;char c;cin>>c>>st>>c>>en>>c; st++;en++;//cout<<st<<" "<<en<<endl;mp[st][en]=1;mp[en][st]=1;G.add(st+n,en,inf);G.add(en+n,st,inf);}for(int i=1;i<=n;i++)G.add(i,i+n,1);for(int i=1+n;i<=2*n;i++){for(int j=i-n+1;j<=n;j++){if(mp[i-n][j]==1)continue;for(int k=2;k<=cnt;k++){//cout<<k<<endl;G.ed[k].val=G.ed[k].v;}G.work(i,j);ans=min(ans,maxflow);//cout<<ans<<endl;}} cout<<ans<<endl;}return 0;
}