LG15645 [ICPC 2022 Tehran R] Network Topology in Hezardastan 题解
\(m\) 个终端，\(n\) 个服务器（\(m\le n\)）。\(m\times n\) 的 0/1 矩阵表示连接终端与服务器是否连接。称大小为 \(m\) 的服务器子集 \(S\) 为可管理的，则存在双射使每个终端连到不同服务器（即服务器子集可以终端完美匹配）。若所有大小为 \(m\) 的子集均可管理，输出
1；否则输出0及任意一个不可管理的大小为 \(m\) 的子集（服务器编号）。\(m\leq 150,n\leq 400,m\leq n\)
是一个二分图，容易想到 Hall 定理，设 \(T\) 为一个终端的非空子集，\(N(T)\) 为所有与 \(T\) 相邻顶点集合，则
\(|N(T)\cap S|\) 是 \(S\) 中与 \(T\) 相连的集合大小（即节点个数），要最小化这个值才能使条件不满足。要最小化的话，需要 \(S\) 选取时尽量不包含 \(N(T)\) 中的节点。记服务器集合全集为 \(U\)
-
若 \(|U\setminus N(T)|=n-|N(T)|\geq m\)，则取 \(S\subseteq U\setminus N(T)\) 即可构造出 \(|N(T)\cap S|=0\)，说明存在不可管理服务器子集。
-
否则 \(S\) 包含 \(|U\setminus N(T)|=n-|N(T)|\) 个不属于 \(N(T)\) 的元素，\(|N(T)\cap S|=m-(n-|N(T)|)\geq |T|\)。
综上可以得到子集均可管理的充要条件
令 \(F(T)=|N(T)|-|T|\)，现在要求 \(F(T)\) 的最小值以及与 \(n-m\) 的关系。
如果构造这样一个网络流模型
源点 \(s\) 向每个终端（左侧点）连一条流量为 \(1\) 的边，每个终端向相连的服务器（右侧点）连一条流量为 \(+\infty\) 的边，每个服务器向汇点连一条流量为 \(1\) 的边。
则求这个模型的最小割，中间终端与服务器的边不会属于最小割，将不属于左侧最小割的点视作 \(T\)，则右侧需要属于最小割的点为 \(N(T)\)，最小割为 \(|N(T)|+(m-|T|)=F(T)+m\)，则需要判断最小割与 \(n\) 的关系。
最小割等于最大流，这个结论应该不必多说了
由于我们没要求 \(T\) 非空，除非原图的匹配就小于 \(m\)（此时不管怎么选都不会有可管理服务器），那么最小割就会等于 \(m\)，对应 \(T\) 为空集，左侧边全部被割掉的情况。现在还需要求非空 \(T\) 的最小割。
这样很好做，每次给一条源点 \(s\) 向终端（左侧点）的边流量改为 \(\infty\)，则这条边就不可能属于最小割，那么 \(T\) 中必须包含这个点，此时求得的最小割对应的集合 \(T\) 就是非空的。
如果其中一个最小割的值 \(<n\)，那么 \(F(T)=最小割-m<n-m\)，就存在不可管理的服务器子集。现在构造出这个子集，左侧不属于最小割的点集即为 \(T\)，计算出 \(T\) 的邻集 \(N(T)\)，优先选择 \(U\setminus N(T)\) 中的点，接着选择 \(N(T)\) 中的点直到 \(m\) 个，根据一开始的证明，选择的 \(N(T)\) 中的点的个数是小于 \(|T|\) 的，这也意味着单独 \(T\) 这个终端子集就一定无法与服务器子集 \(S\) 完美匹配，于是整个终端集合也无法与服务器子集 \(S\) 完美匹配，找到了一组解。
Dinic 算法求二分图匹配单次复杂度 \(O(E\sqrt V)=O(nm\sqrt{n+m})\)，总复杂度 \(O(m^2n\sqrt{n+m})\)，可以通过此题。
#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int,int>ttfa;
const int N=500005;
const int INF=0x3f3f3f3f;
const ll llINF=0x3f3f3f3f3f3f3f3f;struct net_flow{struct chainstar{int nxt,v;ll w;}edge[N];int head[N],now[N],ecnt=1;int S,T,n,dep[N];inline void init(int SS,int TT,int nn){S=SS,T=TT,n=nn,ecnt=1;for(int i=0;i<=n;++i)head[i]=now[i]=0;}inline void addline(int u,int v,ll w){edge[++ecnt].nxt=head[u];head[u]=ecnt;edge[ecnt].v=v;edge[ecnt].w=w;}inline int addedge(int u,int v,ll w){addline(u,v,w);addline(v,u,0ll);return ecnt-1;}queue<int>q;inline bool bfs(){for(int i=0;i<=n;++i)dep[i]=0;dep[S]=1;q.push(S);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(edge[i].w>0&&!dep[v]){dep[v]=dep[u]+1;q.push(v);}}}return dep[T];}ll dfs(int u,ll f){if(u==T)return f;ll tmp=0;for(int i=now[u];i&&f;i=edge[i].nxt,now[u]=i){int v=edge[i].v;if(edge[i].w>0&&dep[v]==dep[u]+1){ll ttf=dfs(v,min(f,edge[i].w));if(ttf==0)dep[v]=n+2;edge[i].w-=ttf;edge[i^1].w+=ttf;tmp+=ttf;f-=ttf;}}return tmp;}ll dinic(){ll sum=0ll;while(bfs()){for(int i=0;i<=n;++i)now[i]=head[i];while(ll tmp=dfs(S,llINF))sum+=tmp;}return sum;}
}flow;int n,m;
int a[155][405];void buildmap(){flow.init(n+m+1,n+m+2,n+m+2);for(int i=1;i<=m;++i){flow.addedge(flow.S,i,1);}for(int i=1;i<=n;++i){flow.addedge(m+i,flow.T,1);}for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){if(a[i][j])flow.addedge(i,j+m,2*n);}}
}int main(){scanf("%d%d",&m,&n);for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){scanf("%d",&a[i][j]);}}buildmap();int sum=flow.dinic();if(sum<m){puts("0");for(int i=1;i<=m;++i){if(i!=1)printf(" ");printf("%d",i);}puts("");return 0;}for(int i=1;i<=m;++i){buildmap();flow.edge[i*2].w=2*n;sum=flow.dinic();if(sum<n){vector<int>lis,tag(n+1,0);for(int j=1;j<=m;++j){if(flow.edge[j*2].w>0){for(int k=1;k<=n;++k){if(a[j][k])tag[k]=1;}}}for(int k=1;k<=n;++k){if(!tag[k])lis.push_back(k);}for(int k=1;k<=n;++k){if(tag[k])lis.push_back(k);}while((int)lis.size()>m)lis.pop_back();sort(lis.begin(),lis.end());puts("0");for(int j=0;j<m;++j){if(j)printf(" ");printf("%d",lis[j]);}puts("");return 0;}}puts("1");return 0;
}
如果证明有错误请多多指正。
另外这个题如果你的写法和原始出题人不一样，大概是只能在洛谷上通过的，这里给洛谷点个赞。其他平台上的 spj 都有问题（包括但不限于答案集合不排序不行，答案集合是正确的仍判错）。