Description
给出一个n+1个点n条边的树，其中每一个度数为1的点为出口。
现在有一些点有逃犯，你需要在一些没有逃犯的点放置警卫，有警卫的点逃犯无法经过。
求若使所有逃犯均无法到达出口，最少需要多少个警卫。
n<=10^5
Solution
为什么我一眼想到最小割=w=
就是所有的逃犯无法到达一些点，那么我们把每个点拆点，x向x’连容量为1的边，割掉这条边表示在这个点放置警卫。
然后对于原图中的每一条边(x,y)，从x’向y连容量为∞的边，表示这条边无法被割掉。
同理从S向每个有逃犯的x’点连容量为∞的边，因为无法在有逃犯的点放置警卫。
然后从每个出口的x’点向T连容量为∞的边，因为可以在出口放置警卫。
然后跑一边最小割就是答案了。如果最小割为∞就是无解。
200000个点的最大流什么的真是梦想_ (:зゝ∠)_
然而它碾过去了2333
好吧我们来讨论正解=w=
随便选一个度数为1的点做根节点，那么所有的出口都是根节点或者叶子节点了。
考虑从下往上递推，每个点可以有三种情况
0：这个点为根的子树中所有的逃犯都无法到达这个点，且不存在一条从这点到叶子节点的路径。
1：存在一条从这点到叶子节点的路径。
2：不存在一条从这点到叶子节点的路径。
那么考虑一个点，如果它的所有儿子都被封死了（就是状态0），那么它自己也就被封死了。
如果这个点有逃犯，那么这个点一下的1点都必须被封死，要不然逃犯可以通过这个点到叶子节点，所以答案加上当前节点状态为1的儿子个数。
否则如果当前点既有状态为1的儿子，又有状态为2的儿子，那么2的逃犯就可以到达这个点，然后从这个点往下逃走。
所以这个点必须被封死。
否则就是只有0/1，0/2的情况，那么除0外是几这个点的状态就是几。
最后如果根节点的状态为2根节点也要封死。
Code
最小割
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
using namespace std;
const int N=2*1e5+5,inf=1e5;
int n,m,S,T,l,x,y,ans,dis[N],d[N],r[N];
int t[N*8],next[N*8],f[N*8],last[N];
void add(int x,int y,int z) {
t[++l]=y;f[l]=z;next[l]=last[x];last[x]=l;
t[++l]=x;f[l]=0;next[l]=last[y];last[y]=l;
}
bool bfs() {
memset(dis,0,sizeof(dis));dis[S]=1;
int i=0,j=1;d[1]=S;
while (i<j) rep(k,d[++i])
if (!dis[t[k]]&&f[k]) dis[t[k]]=dis[d[i]]+1,d[++j]=t[k];
return dis[T];
}
int dinic(int x,int y) {
if (x==T) return y;
int now=0;
rep(i,x) if (f[i]&&dis[t[i]]==dis[x]+1) {
int k=dinic(t[i],min(y,f[i]));
y-=k;now+=k;f[i]-=k;f[i^1]+=k;
if (!y) break;
}
if (!now) dis[x]=-1;
return now;
}
int main() {
scanf("%d%d",&n,&m);n++;S=0;T=2*n+1;l=1;
fo(i,1,n-1) {
scanf("%d%d",&x,&y);x++;y++;
add(x+n,y,inf);add(y+n,x,inf);
r[x]++;r[y]++;
}
fo(i,1,m) scanf("%d",&x),x++,add(S,x+n,inf);
fo(i,1,n) if (r[i]==1) add(i+n,T,inf);
fo(i,1,n) add(i,i+n,1);
while (bfs()) ans+=dinic(S,inf);
if (ans>=inf) printf("-1\n");
else printf("%d\n",ans);
}DP
#include<bits/stdc++.h>
using namespace std;
const int N=100002;
struct node{
int to,ne;
}e[N<<1];
int tot,n,m,x,y,d[N],f[N],h[N],b[N],ans,i;
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++;
}
#define gc getchar
inline int read(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
void add(int x,int y){
e[++tot]=(node){y,h[x]};
h[x]=tot;
}
void dfs(int u,int fa){
int s[3];s[0]=s[1]=s[2]=0;
for (int i=h[u],v;i;i=e[i].ne)
if ((v=e[i].to)!=fa) dfs(v,u),s[f[v]]++;
if (b[u]) ans+=s[1],f[u]=2;
else if (s[1] && s[2]) ans++,f[u]=0;
else if (s[1]) f[u]=1;
else if (s[2]) f[u]=2;
else if (s[0]) f[u]=0;
else f[u]=1;
}
int main(){
n=read();m=read();
for (i=1;i<=n;i++){
x=read();y=read();
add(x,y);add(y,x);
d[x]++;d[y]++;
}
while (m--){
x=read();
if (d[x]==1){
puts("-1");
return 0;
}
b[x]=1;
}
for (i=0;i<=n;i++)
if (d[i]==1){
dfs(i,-1);
if (f[i]==2) ans++;
break;
}
printf("%d",ans);
}
京公网安备 11010502036488号