题目链接
2325. 有向图破坏
爱丽丝和鲍勃正在玩以下游戏。
首先,爱丽丝绘制一个 $N$ 个点 $M$ 条边的有向图。
然后,鲍勃试图毁掉它。
在每一步操作中,鲍勃都可以选取一个点,并将所有射入该点的边移除或者将所有从该点射出的边移除。
已知,对于第 $i$ 个点,将所有射入该点的边移除所需的花费为 $W_i^+$,将所有从该点射出的边移除所需的花费为 $W_i^-$。
鲍勃需要将图中的所有边移除,并且还要使花费尽可能少。
请帮助鲍勃计算最少花费。
输入格式
第一行包含 $N$ 和 $M$。
第二行包含 $N$ 个正整数,第 $i$ 个为 $W_i^+$。
第三行包含 $N$ 个正整数,第 $i$ 个为 $W_i^-$。
接下来 $M$ 行,每行包含两个整数 $a,b$,表示从点 $a$ 到点 $b$ 存在一条有向边。
所有点编号从 $1$ 到 $N$。
图中可能由重边或自环。
输出格式
第一行输出整数 $W$,表示鲍勃所需的最少花费。
第二行输出整数 $K$,表示鲍勃需要进行的操作步数。
接下来 $K$ 行,每行输出一个鲍勃的具体操作。
如果操作为将所有射入点 $i$ 的边移除,则输出格式为 i +
。
如果操作为将所有从点 $i$ 射出的边移除,则输出格式为 i -
。
如果答案不唯一,则输出任意一种即可。
数据范围
$1 \le N \le 100$,
$1 \le M \le 5000$,
$1 \le W_i^+,W_i^- \le 10^6$
输入样例:
3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3
输出样例:
5
3
1 +
2 -
2 +
解题思路
最小割,最小权点覆盖,二分图
最小点权覆盖,即选择这样的点集,使得所有边都至少有一个端点在点集内,且这样的点集的权值之和最小
同样,最小权点覆盖在一般图中是 NPC 问题,针对二分图有很好的效果
对于一个二分图,考虑转换为流网络,建立一个源点 $s$,$s$ 向二分图左部的所有点连边,容量为点权,同样地,建立一个汇点 $t$,二分图右部的所有点向 $t$ 连边,容量为点权,原二分图中的边在流网络中容量足够大,可以发现:这样的建图方式与 961. 最大获利 中的建图方式类似,即证明时只用考虑简单割和极小点覆盖集(即有一些点明显可以从删去)之间的关系
证明:简单割和极小点覆盖集可以相互转换
简单割可以转换为极小点覆盖集
对于一个简单割 $[S,T]$,对于一个割边 $[x,y]$,由于是简单割,则一定有 $x=s$ 或 $y=t$,如果 $x=s$ 则将点 $y$ 加入点集,否则将 $x$ 加入点集中,$\color{red}{这样的点集是否为点覆盖集?}$假设在二分图中存在一条边 $x,y$,$x$ 和 $y$ 都没在点集中,即该条边没有被覆盖,则说明 $x$ 和 $y$ 都在割的 $S$ 或者 $T$ 部分,假设 $x$ 和 $y$ 都在 $S$ 部分,又由于 $y$ 会连向 $t$,此时存在割边 $x$ 和 $y$ 都在 $T$ 部分同理,矛盾,故 $x$ 和 $y$ 至少有一个点会在点集中,故该点集为点覆盖集
极小点覆盖集可以转换为简单割
对于极小点覆盖集中的一个点 $x$,如果该点在左部,则将 $s->x$ 作为割边,否则将 $x->t$ 作为割边,然后构造 $S$ 部分,从 $s$ 出发,在不经过割边的前提下将所有能到达的点作为 $S$ 部分,否则作为 $T$ 部分,$\color{red}{这样的割是否为简单割}$,假设存在一条边可以从 $s$ 走到 $t$,即存在这样的路径 $s->x->y->t$,这就说明 $x->y$ 这条边没有被覆盖,与极小点覆盖集矛盾,故不存在这样的路径,且所有的割边容量有限,即这样的割是简单割
故简单割与极小点覆盖集一一对应
不难发现数量上也是一一对应的,故求最小权点覆盖等价于求最小割
本题难在建图:拆点,将所有点拆分为出点和入点,所有的出点作为二分图的左部,入点作为二分图的右部,建立源点 $s$ 和汇点 $t$,对于原图中的一条有向边 $x->y$,要将这条边移除,可以是 $W_x^-$(从 $x$ 射出的边的代价) 的代价,也可以是 $W_y^+$(射入 $y$ 的边的代价) 的代价,即对应流网络中 $s$ 向所有这样的 $x$ 连一条容量为 $W_x^-$ 的边,所有这样的 $y$ 向 $t$ 连一条容量为 $W_y^+$ 的边,其余边容量足够大即可。不难发现其正是求最小权点覆盖,因为删除或者覆盖的边对应二分图中的边
另外,本题还要求输出方案,而且还要区分对应二分图中的左部和右部,不妨先将整个割找出来,遍历所有的割边,如果存在一个端点为 $s$,说明另外一个端点在右部,否则在左部
需要注意:dinic
算法求解二分图问题时间复杂度为 $O(m\sqrt{n})$
- 时间复杂度:$O(m\sqrt{n})$
代码
// Problem: 有向图破坏
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/2327/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=205,M=(5005+N)*2,inf=1e9;
int n,m,S,T;
int h[N],ne[M],f[M],e[M],idx;
int d[N],hh,tt,q[N],cur[N];
bool v[N];
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
memset(d,-1,sizeof d);
d[S]=hh=tt=0;
q[0]=S;
cur[S]=h[S];
while(hh<=tt)
{
int x=q[hh++];
for(int i=h[x];~i;i=ne[i])
{
int y=e[i];
if(d[y]==-1&&f[i])
{
d[y]=d[x]+1;
cur[y]=h[y];
if(y==T)return true;
q[++tt]=y;
}
}
}
return false;
}
int dfs(int x,int limit)
{
if(x==T)return limit;
int flow=0;
for(int i=cur[x];~i&&flow<limit;i=ne[i])
{
cur[x]=i;
int y=e[i];
if(d[y]==d[x]+1&&f[i])
{
int t=dfs(y,min(f[i],limit-flow));
if(!t)d[y]=-1;
f[i]-=t,f[i^1]+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())while(flow=dfs(S,inf))res+=flow;
return res;
}
void dfs(int x)
{
v[x]=true;
for(int i=h[x];~i;i=ne[i])
if(!v[e[i]]&&f[i])dfs(e[i]);
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
S=0,T=2*n+1;
int w;
for(int i=1;i<=n;i++)
{
scanf("%d",&w);
add(i+n,T,w);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&w);
add(S,i,w);
}
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b+n,inf);
}
printf("%d\n",dinic());
dfs(S);
int cnt=0;
for(int i=0;i<idx;i+=2)
{
int x=e[i^1],y=e[i];
if(v[x]&&!v[y])cnt++;
}
printf("%d\n",cnt);
for(int i=0;i<idx;i+=2)
{
int x=e[i^1],y=e[i];
if(v[x]&&!v[y]&&y==T)printf("%d +\n",x-n);
}
for(int i=0;i<idx;i+=2)
{
int x=e[i^1],y=e[i];
if(v[x]&&!v[y]&&x==S)printf("%d -\n",y);
}
return 0;
}