[结论 + 网络流] UOJ168. 【UR #11】元旦老人与丛林

好题。先要猜到结论才可做。

有个很厉害的结论是,对于任意子图都满足 \(|E|\le 2|V|-2\) ,则一定是丛林。证明看题解。

感觉有许多结论都是必要性很显然,充分性不显然,猜结论可以往这个方向想。

然后就瞬间变可做了,现在只需求 \(|E| - 2|V|\) 的最大值。

容易想到套最大权闭合子图的模型:

对每条边建点,边的点权为 \(1\) ,原图点的点权为 \(-2\) ,选边的条件是两端点都选了。

注意到这样有个问题,就是可能求出来只选了一个 \(-2\) 的点,就不能验证了。

我们可以强制选取某一个点,即把某这给点权设为 \(0\)。这样就正常了。

枚举点每次刷最大流肯定 \(T\)

每次只改了一条边的权,有退流这种操作,具体见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=7005,maxe=50005;
int fir_pos[maxn],fir[maxn],nxt[maxe],son[maxe],cap[maxe],fw[maxe],tot=1,INF;
void add(int x,int y,int w){
son[++tot]=y; cap[tot]=w; fw[tot]=0; nxt[tot]=fir[x]; fir[x]=tot;
son[++tot]=x; cap[tot]=0; fw[tot]=0; nxt[tot]=fir[y]; fir[y]=tot;
}
int d[maxn],N,S,T;
int q[maxn];
bool Bfs(int S,int T){
memset(d,63,sizeof(d)); INF=d[0];
q[q[0]=1]=S; d[S]=0;
for(int i=1;i<=q[0];i++){
int x=q[i];
for(int j=fir[x];j;j=nxt[j])
if(cap[j]>fw[j]&&d[son[j]]==INF)
d[son[j]]=d[x]+1, q[++q[0]]=son[j];
}
return d[T]!=INF;
}
inline int min(int x,int y){
return x<y?x:y;
}
int Dfs(int x,int flw,int T){
if(x==T||!flw) return flw;
int res=0,t;
for(int j=fir[x];j;j=nxt[j])
if(d[x]+1==d[son[j]]&&(t=Dfs(son[j],min(flw,cap[j]-fw[j]),T))>0){
flw-=t; res+=t; fw[j]+=t; fw[j^1]-=t;
if(!flw) { d[x]=INF; break; }
}
return res;
}
int Dinic(int S,int T,int lim){
int res=0;
while(res<lim&&Bfs(S,T)){
res+=Dfs(S,lim-res,T);
}
return res;
}
int n,m;
int main(){
n=getint(); m=getint();
N=n+m+2; S=n+m+1; T=S+1;
for(int i=1;i<=n;i++) add(i,T,2);
for(int i=1;i<=m;i++){
int x=getint(),y=getint();
add(S,n+i,1); add(n+i,x,1e9); add(n+i,y,1e9);
}
int Allflw=Dinic(S,T,1e9);
if(Allflw!=m) return puts("No"),0;
for(int i=1;i<=n;i++){
int k=fw[i<<1];
Allflw-=Dinic(i,S,k);
fw[i<<1]=fw[i<<1|1]=cap[i<<1]=0;
Allflw+=Dinic(S,T,k);
if(Allflw!=m) return puts("No"),0;
cap[i<<1]=2;
}
puts("Yes");
return 0;
}