题意
定义一张图的密度为它的边数与点数的比值。
给定一张 \(n\) 个点、\(m = dn\) 条边的无向图，记点集为 \(V\)。你需要判断，任取 \(V\) 的非空真子集 \(X\)，\(X\) 的导出子图的密度是否一定严格小于 \(d\)。
多测，\(1 \leq n, d, \sum m \leq 50000\)。
题解
对于一张流网络，记 \(s, t\) 为源汇点，\(V\) 为点集，\(|f|\) 表示可行流 \(f\) 的流量，\(f(u, v)\) 表示边 \((u, v)\) 的流量，\(f(S, T)\) 表示割集 \([S, T]\) 的流量，\(c(u, v)\) 表示边 \((u, v)\) 的容量，\(c(S, t)\) 表示割 \([S, T]\) 的容量。那么有以下两个引理。
引理 1. 任取可行流 \(f\) 和割集 \([S, T]\)，那么有 \(|f| = f(S, T)\)。
证明（引理 1）
对于两个点集 \(X, Y\)，定义 \(f(X, Y) = \sum_{u \in X} \sum{v \in Y} f(u, v) - \sum_{u \in X} \sum_{v \in Y} f(v, u)\)。那么显然有：
- \(f(X, X) = 0\)；
- 对两个不交点集 \(A, B\)，有 \(f(X, A) + f(X, B) = f(X, A \cup B)\)，\(f(A, X) + f(B, X) = f(A \cup B, X)\)。
直接上公式：\(f(S, T) = f(S, V) - f(S, S) = f(S, V) = f(\{s\}, V) + f(S \setminus \{s\}, V)\)。
对于第一项，\(f(\{s\}, V)\) 即为从源点 \(s\) 流出去的流量，即 \(|f|\)。
对于第二项，集合 \(S \setminus \{s\}\) 一定不包含 \(s, t\) 两点，因此其中每个点 \(u\) 必然满足流量守恒，代入定义式得 \(f(\{u\}, V) = 0\)。由性质 2 得 \(f(S \setminus \{s\}, V) = 0\)。
综上，\(f(S, T) = |f| + 0 = |f|\)，得证。
引理 2. 任取最大可行流 \(f\) 和最小割，每条割边必然满流。
证明（引理 2）
由最大流最小割定理，\(c(S, T) = |f|\)。由引理 1，\(f(S, T) = |f|\)。因此 \(f(S, T) = c(S, T)\)。
如果任取割集 \([S', T']\)，那么有 \(f(S', T') = \sum_{u \in S'} \sum_{v \in T'} f(u, v) - \sum_{u \in S'} \sum_{v \in T'} f(v, u) \leq \sum_{u \in S'} \sum_{v \in T'} f(u, v) \leq \sum_{u \in S'} \sum_{v \in T'} c(u, v) = c(S', T')\)。显然取等条件为：对 \(u \in S', v \in T'\)，有 \(f(u, v) = c(u, v)\)，\(f(v, u) = 0\)。
由于在最小割中有 \(f(S, T) = c(S, T)\)，将取等条件代入即可得到结论。
回到本题。如果将条件改成“密度小于等于 \(d\)”，这就变成了最大密度子图的板子题。套路地，我们将条件转化为判断 \(|E| - d|V| \leq 0\)。新建二分图，将原图的边视作二分图的左部点，将原图的点视作二分图的右部点，对原图的一条边 \(e = (u, v)\)，在新图上连有向边 \((e, u)\) 和 \((e, v)\)。给左部点赋权值 \(1\)，给右部点赋权值 \(-d\)，我们只需要判断该图的最大权闭合图是否小于等于 \(0\) 即可。
问题在于我们不能判断是否存在密度恰为 \(d\) 的情况：我们发现整张图的密度就是 \(d\)，而题目中让你选的点集为 \(V\) 的真子集。因此如果直接套用上述做法，你选出来的密度为 \(d\) 的子图可能就是原图本身，与题目条件不符。
我们相当于要做这么一件事情：判断密度恰为 \(d\) 的子图是否只有原图和空图两种。前者相当于钦定每条边都选，后者相当于钦定每条边都不选。对应到流网络中，前者相当于钦定割边必须恰为右部点到汇点的所有边，后者相当于钦定割边必须恰为源点到左部点的所有边。也就是说，一个流网络合法，当且仅当不存在一个既包含左部的边、又包含右部的边的最小割。
考虑钦定是否割掉左部的第一条边。对于一个合法的流网络而言，若钦定不割掉该边，那么割掉的边全是右部的边；若钦定割掉该边，那么割掉的边全是左部的边。显然这个条件是充要的，也就是说如果流网络不合法，那么上述至少一个命题不成立。
于是考虑分别判定这两个命题是否成立。
对于第一个命题，钦定割掉该边相当于直接删去该边，并在删边后的图上重新跑流网络。此时我们只需要判定是否存在一个左部的边使得他在某个最小割中。由引理 2，只需判定是否存在一个左部的边满流即可。事实上有个更简单的判定方法：直接从源点出发跑一遍 Dinic 里面的那个 bfs，判断是否存在一个无法到达的左部点，容易发现这是等价的。
对于第二个命题，同理等价于判定是否存在一个右部的边边满流。
于是就做完了。时间复杂度为 \(\Theta(mn \sqrt{mn})\)。
代码
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int P=50003,N=P*2,M=P*4,PIN=5e8;
struct Edge{
int u,v;
}edge[P];
int d,n,m,ls1[N],ls2[N]; bool bj[N];
int len_list=0,e[M*2],w[M*2],ne[M*2],h[N];
int get_edge(int u){ return u+2; }
int get_node(int u){ return u+m+2; }
void add(int a,int b,int val){
e[len_list]=b;
w[len_list]=val;
ne[len_list]=h[a];
h[a]=len_list++;
}
void add_once(int a,int b,int val){
add(a,b,val),add(b,a,0);
}
bool bfs(int S,int T,int dis[N],int cur[N],bool opt=0){
int i,s1; queue<int> dl;
for(i=1;i<=m+n+2;i++) bj[i]=0;
dl.push(S),bj[S]=1;
dis[S]=0,cur[S]=h[S];
while(!dl.empty()){
s1=dl.front(),dl.pop();
for(i=h[s1];i>=0;i=ne[i])
if(!bj[e[i]]&&w[i^opt]>0){
dl.push(e[i]),bj[e[i]]=1;
dis[e[i]]=dis[s1]+1;
cur[e[i]]=h[e[i]];
if(e[i]==T) return 1;
}
}
return 0;
}
int dfs(int u,int limit,int T,int dis[N],int cur[N]){
if(u==T) return limit;
int i,s1,ans=0;
for(i=cur[u];i>=0&&ans<limit;i=ne[i]){
cur[u]=i;
if(dis[e[i]]==dis[u]+1&&w[i]>0){
s1=dfs(e[i],min(limit-ans,w[i]),T,dis,cur);
if(!s1) dis[e[i]]=-1;
w[i]-=s1,w[i^1]+=s1,ans+=s1;
}
}
return ans;
}
int Dinic(int S,int T){
int ans=0;
while(true){
int dis[N]={0},cur[N]={0},s1;
if(!bfs(S,T,dis,cur)) break;
while(s1=dfs(S,PIN,T,dis,cur)) ans+=s1;
}
return ans;
}
int main(){
// freopen("sparser.in","r",stdin);
// freopen("sparser.out","w",stdout);
int i,t;
for(scanf("%d",&t);t>0;t--){
scanf("%d%d",&n,&d),m=n*d;
for(i=1;i<=m;i++)
scanf("%d%d",&edge[i].u,&edge[i].v);
for(len_list=0,i=1;i<=m+n+2;i++) h[i]=-1;
for(i=1;i<=m;i++) add_once(1,get_edge(i),1);
for(i=1;i<=n;i++) add_once(get_node(i),2,d);
for(i=1;i<=m;i++){
add_once(get_edge(i),get_node(edge[i].u),PIN);
add_once(get_edge(i),get_node(edge[i].v),PIN);
}
if(Dinic(1,2)<m){ puts("No"); continue; }
for(len_list=0,i=1;i<=m+n+2;i++) h[i]=-1;
for(i=2;i<=m;i++) add_once(1,get_edge(i),1);
for(i=1;i<=n;i++) add_once(get_node(i),2,d);
for(i=1;i<=m;i++){
add_once(get_edge(i),get_node(edge[i].u),PIN);
add_once(get_edge(i),get_node(edge[i].v),PIN);
}
Dinic(1,2),bfs(2,1,ls1,ls2,1);
for(i=1;i<=n;i++)
if(!bj[get_node(i)]) break;
if(i<=n){ puts("No"); continue; }
add_once(1,get_edge(1),PIN);
for(Dinic(1,2),i=1;i<=m;i++)
if(!bj[get_edge(i)]) break;
puts((i<=m)?"No":"Yes");
}
// fclose(stdin);
// fclose(stdout);
return 0;
}