CF786E ALT
eee_hoho
2021-03-28 08:25:51
首先建图很显然，源点连居民流量为 $1$ ，割掉就相当于选居民，守卫连汇点流量为 $1$ ，割掉相当于选守卫，然后居民向路径上得每个守卫连正无穷的边，求最小割就可以了。
这样子边数是 $n^2$ ，用树剖优化建图就是 $n\log^2n$ 的了。
然后输出方案，最小割求方案不是很套路吗，就是[这道题](https://www.luogu.com.cn/problem/P4126)，别的题解解释的太麻烦了。
对残量网络中未满流的边缩点，那么我们可以得到最小割的必须边和可行边。
可行边是边的两个端点不在同一个 SCC 中。
必须边是边的两个端点一个和源点在同一个 SCC ，另一个和汇点在同一个 SCC 。
然后方案就出来了，选取所有必须边然后选可行边知道最大流就可以了。
**Code**
``` cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
const int N = 2e4;
const int inf = 1e9;
using namespace std;
struct edges
{
int to,id;
}edge[N * 2 + 5];
int n,m,nxt[N * 2 + 5],head[N + 5],edge_cnt,size[N + 5],top[N + 5],son[N + 5],dep[N + 5],fa[N + 5],dfn[N + 5],dfc,S,T,idc,ID[N + 5],val[N + 5],bk[N * 20 + 5],id[N * 20 + 5];
vector <int> a1,a2;
namespace F
{
const int N = 3e6;
const long long inf = 2e18;
struct edges
{
int to;
long long cost;
}edge[N * 2 + 5];
int nxt[N * 2 + 5],head[N + 5],edge_cnt = 1,dis[N + 5],q[N + 5],cur[N + 5],S,T,dfn[N + 5],dfc,low[N + 5],stk[N + 5],top,co[N + 5],cnt,Vis[N + 5];
void add_edge(int u,int v,long long w)
{
edge[++edge_cnt] = (edges){v,w};
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void add(int u,int v,long long w)
{
add_edge(u,v,w);
add_edge(v,u,0);
}
int bfs()
{
for (int i = 1;i <= idc;i++)
cur[i] = head[i],dis[i] = 0;
int l = 1,r = 0;
dis[S] = 1;
q[++r] = S;
while (l <= r)
{
int u = q[l++];
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost;
if (w && !dis[v])
{
dis[v] = dis[u] + 1;
q[++r] = v;
}
}
}
return dis[T];
}
long long dfs(int u,long long flow)
{
if (u == T)
return flow;
long long sm = 0;
for (int &i = cur[u];i;i = nxt[i])
{
int v = edge[i].to;
long long w = edge[i].cost;
if (dis[v] == dis[u] + 1 && w)
{
long long res = dfs(v,min(w,flow));
edge[i].cost -= res;
edge[i ^ 1].cost += res;
sm += res;
flow -= res;
if (!flow)
break;
}
}
return sm;
}
long long dinic(int s,int t)
{
S = s;T = t;
long long ans = 0;
while (bfs())
ans += dfs(S,inf);
return ans;
}
void clear()
{
edge_cnt = 1;
for (int i = 1;i <= idc;i++)
head[i] = 0;
idc = 0;
}
void tarjan(int u)
{
low[u] = dfn[u] = ++dfc;
stk[++top] = u;
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost;
if (!w)
continue;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else
if (!co[v])
low[u] = min(low[u],dfn[v]);
}
if (low[u] == dfn[u])
{
co[u] = ++cnt;
while (stk[top] != u)
co[stk[top--]] = cnt;
top--;
}
}
void solve(int s,int t,int k)
{
for (int i = 1;i <= idc;i++)
if (!dfn[i])
tarjan(i);
for (int i = head[s];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost;
if (!w && co[v] == co[t])
a1.push_back(id[v]),k--,Vis[v] = 1;
}
for (int i = head[t];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost;
if (w && co[v] == co[s])
a2.push_back(bk[v]),k--,Vis[v] = 1;
}
if (k)
{
for (int i = head[s];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost;
if (!w && co[v] != co[s] && !Vis[v] && k)
a1.push_back(id[v]),k--;
}
for (int i = head[t];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost;
if (w && co[v] != co[t] && k)
a2.push_back(bk[v]),k--;
}
}
}
}
struct Seg
{
int id[N * 4 + 5];
#define zrt k << 1
#define yrt k << 1 | 1
void build(int k,int l,int r)
{
id[k] = ++idc;
if (l == r)
{
F::add(id[k],T,1);
bk[id[k]] = val[l];
return;
}
int mid = l + r >> 1;
build(zrt,l,mid);
build(yrt,mid + 1,r);
F::add(id[k],id[zrt],inf);
F::add(id[k],id[yrt],inf);
}
void update(int k,int l,int r,int x,int y,int z)
{
if (x > y)
return;
if (l >= x && r <= y)
{
F::add(z,id[k],inf);
return;
}
int mid = l + r >> 1;
if (x <= mid)
update(zrt,l,mid,x,y,z);
if (y > mid)
update(yrt,mid + 1,r,x,y,z);
}
}tree;
void add_edge(int u,int v,int id)
{
edge[++edge_cnt] = (edges){v,id};
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void dfs1(int u,int f)
{
fa[u] = f;
dep[u] = dep[f] + 1;
size[u] = 1;
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i].to,id = edge[i].id;
if (v == f)
continue;
ID[v] = id;
dfs1(v,u);
size[u] += size[v];
if (size[v] > size[son[u]])
son[u] = v;
}
}
void dfs2(int u,int to)
{
top[u] = to;
dfn[u] = ++dfc;
val[dfc] = ID[u];
if (son[u])
dfs2(son[u],to);
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i].to;
if (v == fa[u] || v == son[u])
continue;
dfs2(v,v);
}
}
void update(int x,int y,int z)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x,y);
tree.update(1,1,n,dfn[top[x]],dfn[x],z);
x = fa[top[x]];
}
if (dfn[x] > dfn[y])
swap(x,y);
tree.update(1,1,n,dfn[x] + 1,dfn[y],z);
}
int main()
{
scanf("%d%d",&n,&m);
int u,v;
for (int i = 1;i < n;i++)
{
scanf("%d%d",&u,&v);
add_edge(u,v,i);
add_edge(v,u,i);
}
dfs1(1,0);
dfs2(1,1);
S = ++idc;T = ++idc;
tree.build(1,1,n);
for (int i = 1;i <= m;i++)
{
scanf("%d%d",&u,&v);
idc++;
id[idc] = i;
F::add(S,idc,1);
update(u,v,idc);
}
int x = F::dinic(S,T);
cout<<x<<endl;
F::solve(S,T,x);
cout<<a1.size()<<" ";
for (int i = 0;i < a1.size();i++)
printf("%d ",a1[i]);
cout<<endl<<a2.size()<<" ";
for (int i = 0;i < a2.size();i++)
printf("%d ",a2[i]);
return 0;
}
```