给出个无向图，问是否存在一种方式把边集划分成两个不为空的边集，使得两个边集分别都是森林。
(nle 2000,mle 2n)
有结论：当且仅当每个子图都满足(|E|le 2|V|-2)的时候，存在方案。
以下证明其充分性：
考虑归纳，即已经证明(|V|)更小的满足条件。以下称(|E|=2|V|-2)的图是满的。
设当前图为(G)。
对于1度点，可以直接删掉，连着的边任意分；对于2度点，也可以删掉，连着的边分在不同边集。又因(|E|le 2|V|-2)，所以一定存在3度点。任意选一个3度点，记为(u)，它连出去的三个点为(a,b,c)。
记(G_1)表示(G)中删去(u)形成的子图。
引理1：如果图中存在两个在点相交的满子图，那么它们的并也是满的。
设两个子图以及它们的交、并分别为(G_1=(V_1,E_1),G_2,G_3,G)。
要证(|E|=2|V|-2)。由(|E|le 2|V|-2)得(|E_1|+|E_2|-|E_3|le 2(|V_1|+|V_2|-|V_3|)-2)。
由(G_1,G_2)为满子图，联立上式得(|E_3|ge 2|V_3|-2)。
又因为(|E_3|le 2|V_3|-2)，所以(|E_3|=2|V_3|-2)，进而(|E|=2|V|-2)。
引理2：(a,b,c)中至少存在一对点(x,y)，使得(G_1)不存在满的子图同时包含(x,y)。
反证。假设两两之间都存在一个满的子图包含它们，把这三个子图求并，由引理1得到这个并也是满的，有(|E|=2|V|-2)。
往这个图中加入点(u)以及三条边，此时(|E|=2|V|-1)，不符合。
构造方法如下：把((x,y))丢入(G_1)中，构造出方案之后，对于((x,y))所在的那个边集，把((x,y))改成((u,x),(u,y))；另一个边集丢入剩下那条边。
接下来判定的时候，可以转化为最大权闭合非空子图问题：搞个(n+m)个点的图，对于一条边(e_i=(u,v))，连((e_i,u),(e_i,v))，给点赋权(-2)，给边赋权(1)，然后跑最大权闭合非空子图。如果跑出来结果大于(-2)则不合法。
因为子图要非空，直接跑只会跑到(0)。于是要枚举一个点，强制它选，并且将其权值变成(0)，然后再跑最大权闭合子图。因为是二分图所以跑dinic时间是(O(nsqrt n m))。
也可以用类似SDOI2014 LIS的网络流退流做法。时间是(O(sqrt nm+nm))。
我的退流方法：
枚举(i)，先判断((i,T))是否为割边，如果是，强制它选，答案一样，如果不是：
设(F)为总流量，(f)为((i,T))当前流量。将((i,T))清空，跑(flow(i,T,f))。新的流量可视作(F-f+flow(i,T,f))。
可以看做强制不走这条边，用到达这条边的流量尝试跑到(T)。
注意搞完之后跑(flow(T,i,f))回退。
int F=flow(s,t),mx=-2;
for (int i=1;i<=n;++i){
if (!bfs(i,t))
mx=max(mx,m-F);
else{
int f=rev(de[i])->c;
de[i]->c=rev(de[i])->c=0;
mx=max(mx,m-(F-f+flow(i,t,f))-2);
flow(t,i,f);
de[i]->c=2-f,rev(de[i])->c=f;
}
if (mx>-2)
break;
}
人家的退流方法：
(flow(i,S,f))，再(flow(S,T))。就是直接退掉，然后再找新的增广路，不需要考虑是否为割边。
搞完之后把边加回来，也没必要立刻重新跑一次最大流，因为下一次影响答案前会跑一次(flow(S,T))。
下面的代码之所以不规定(flow(i,S))的流量上限，是因为(i)的出边只有一条，((i,T))的流量等于(flow(i,S))。
int F=flow(s,t),mx=-2;
for (int i=1;i<=n;++i){
de[i]->c=rev(de[i])->c=0;
F-=flow(i,s);
F+=flow(s,t);
mx=max(mx,m-F-2);
de[i]->c=2;
if (mx>-2)
break;
}
贴一个总的代码：
using namespace std;
#include <bits/stdc++.h>
#define N 2009
#define INF 1000000000
int n,m;
int nn,s,t;
struct EDGE{
int to,c;
EDGE *las;
} e[N*7*2];
int ne;
EDGE *last[N*3];
void link(int u,int v,int c){
e[ne]={v,c,last[u]};
last[u]=e+ne++;
}
#define rev(ei) (e+(int((ei)-e)^1))
EDGE *de[N];
EDGE *cur[N*3];
int dis[N*3];
int S,T;
bool bfs(int s,int t){
static queue<int> q;
for (int i=1;i<=nn;++i)
cur[i]=last[i];
memset(dis,127,sizeof(int)*(nn+1));
while (!q.empty()) q.pop();
q.push(s);
dis[s]=0;
while (!q.empty()){
int x=q.front();
q.pop();
for (EDGE *ei=last[x];ei;ei=ei->las)
if (ei->c && dis[ei->to]>=INF){
dis[ei->to]=dis[x]+1;
if (ei->to==t)
return 1;
q.push(ei->to);
}
}
return 0;
}
int dfs(int x,int s){
if (x==T)
return s;
int have=0;
for (EDGE *&ei=cur[x];ei;ei=ei->las)
if (ei->c && dis[ei->to]==dis[x]+1){
int t=dfs(ei->to,min(ei->c,s-have));
ei->c-=t,rev(ei)->c+=t,have+=t;
if (have==s)
return s;
}
return have;
}
int flow(int _S,int _T,int lim=INF){
S=_S,T=_T;
memset(cur,0,sizeof(EDGE*)*(nn+1));
int res=0;
while (lim && bfs(S,T)){
int t=dfs(S,lim);
res+=t,lim-=t;
}
return res;
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
nn=n+m;
s=++nn,t=++nn;
ne=0;
memset(last,0,sizeof(EDGE*)*(nn+1));
for (int i=1;i<=n;++i)
de[i]=e+ne,link(i,t,2),link(t,i,0);
for (int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
link(s,i+n,1),link(i+n,s,0);
link(i+n,u,INF),link(u,i+n,0);
link(i+n,v,INF),link(v,i+n,0);
}
int F=flow(s,t),mx=-2;
for (int i=1;i<=n;++i){
de[i]->c=rev(de[i])->c=0;
F-=flow(i,s);
F+=flow(s,t);
mx=max(mx,m-F-2);
de[i]->c=2;
if (mx>-2)
break;
}
if (mx>-2)
printf("No
");
else
printf("Yes
");
return 0;
}