[GYM101667J] Strongly Matchable
最后的轉化太妙了
題意：一個 \(2n\) 個點的無向圖，判斷將任意 \(n\) 個點染成黑色，另外的 \(n\) 個點染成白色是否都存在完美匹配。
\(N(S)\) 表示與在 \(S\) 這個點集中的點存在連邊且不在 \(S\) 中的點的點集
考慮 hall 定理，取一個大小 \(\le n\) 的點集 \(S\)，那么對應的最小的鄰域一定是 \(|N(S)|-(n-|S|)\)，則列出不等式：
\[|S| \le |N(S)|-(n-|S|)
\]
也就是：
\[n \le |N(S)|
\]
所以考慮枚舉一個 \(|N(S)| < n\)， 若將 \(N(S)\) 中的點刪完之后剩下的圖不連通，由于剩下的點個數 \(<2n\)，所以必定存在一個點集 \(S\) 的大小小于 \(n\)，所以用網絡流解決一個圖最少刪掉多少個點能使其不連通即可（點連通度）。
代碼常熟有點大，只做參考
點擊查看代碼
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
return x*f;
}
const int inf=1e9,N=2e2+5,M=2e4+5;
int n,m;
int head[N],cnt=1;
struct edge{int v,nxt,w;}p[M*2],q[M*2];
inline void add_edge(int u,int v,int w){
p[++cnt]={v,head[u],w};
head[u]=cnt;
p[++cnt]={u,head[v],0};
head[v]=cnt;
}
int S,T,du[N],vis[N],cur[N];
inline bool bfs(){
queue<int> qu;
qu.push(S);
for(int i=1;i<=2*n;i++) vis[i]=du[i]=0;
while(!qu.empty()){
int x=qu.front();
qu.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=q[i].nxt){
int v=p[i].v;
if(!q[i].w) continue;
if(!vis[v]){
du[v]=du[x]+1;
qu.push(v);
}
}
}
return vis[T];
}
inline int dfs(int x,int flow){
if(x==T) return flow;
int num=0;
for(int i=cur[x];i;i=q[i].nxt){
cur[x]=i;
int v=q[i].v,w=q[i].w;
if(du[v]==du[x]+1){
int expand=dfs(v,min(flow,w));
q[i].w-=expand;
q[i^1].w+=expand;
num+=expand;
flow-=expand;
if(!flow) return num;
}
}
return num;
}
inline int Dinic(){
for(int i=2;i<=cnt;i++) q[i]=p[i];
int res=0;
while(bfs()){
res+=dfs(S,inf);
memcpy(cur,head,sizeof(head));
}
return res;
}
int V[N];
vector<int> ed[N];
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++) add_edge(i,i+n,1);
for(int i=1;i<=m;i++){
int u=read(),v=read();
add_edge(u+n,v,inf);
add_edge(v+n,u,inf);
ed[u].push_back(v);
ed[v].push_back(u);
}
for(auto v:ed[1]) V[v]=1;
int ans=inf;
for(int s=1;s<=n;s++){
for(int i=1;i<=n;i++) V[i]=0;
for(auto v:ed[s]) V[v]=1;
V[s]=1;
for(int t=1;t<=n;t++){
if(V[t]) continue;
S=n+s,T=t;
ans=min(ans,Dinic());
}
}
if(ans*2<n) puts("-1");
else puts("1");
}
浙公網安備 33010602011771號