关键词:最大权闭合子图 最小割
相关题目:$Luogu2762$ $Loj6001$

Solution

这道题是求一个最大权闭合子图
然后可以转化为最小割问题,求一下最大流就可以了

具体细节不谈

比较麻烦的是如何求方案
似乎有点难想
我们在残量网络中从源点沿着所有有残余容量的边遍历,
所有遍历到的点所代表的实验和器材都是要用到的

为什么这么做呢?
首先所有源点的有残余容量的出边所指向的实验肯定是要做的,
这样就会遍历到这些实验要用到的器材,
然后这些器材的一部分费用可能会由没有遍历到的实验的盈利承担
这时就会从这些器材的反向边遍历到那些实验,
那些实验需要的器材又会被遍历到

然后就如此反复反复咯,最后所有被遍历到的点都是需要的

代码

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
#include <cstdio>
#include <ctype.h>
#include <algorithm>
using namespace std;
inline int read(int &x){
x=0;
int f=1; char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-48, ch=getchar();
return ch!='\r'&&ch!='\n';
}

int to[1000],nxt[1000],head[200],w[1000],s,t,dep[200],cunt[200];
int cur[200],sum,maxflow,x,n,m,cnt=1,a[600],vis[110];
inline void add(int u,int v,int val){
to[++cnt]=v,w[cnt]=val,
nxt[cnt]=head[u],head[u]=cnt;
}
inline void link(int u,int v,int val){
add(u,v,val),add(v,u,0);
}
int dfs(int u,int maxflow){
if(u==t) return maxflow;
int flow=0;
for(int i=cur[u];i;i=nxt[i]){
cur[u]=i;
if(w[i]&&dep[to[i]]+1==dep[u]){
int now=dfs(to[i],min(w[i],maxflow-flow));
flow+=now;
w[i]-=now;
w[i^1]+=now;
if(maxflow==flow) return flow;
}
}
cur[u]=head[u];
if(--cunt[dep[u]]==0) dep[s]=n+m+2;
cunt[++dep[u]]++;
return flow;
}
void dfs(int u){
vis[u]=1;
for(int i=head[u];i;i=nxt[i])
if(!vis[to[i]]&&w[i]) dfs(to[i]);
}
int main(int argc, char const *argv[])
{
read(n),read(m);
s=n+m+1;
t=s+1;cunt[0]=t;
for(int i=1;i<=n;i++){
read(x),link(s,i,x),sum+=x;
while(read(x)) link(i,x+n,2e9);
link(i,x+n,2e9);
}
for(int i=1;i<=m;i++)
read(a[i]),link(i+n,t,a[i]);
while(dep[s]<n+m+2)
maxflow+=dfs(s,2e9);
for(int i=1;i<=n;i++)
if(vis[i]) printf("%d ",&i);
puts("");
for(int i=n+1;i<=n+m;i++)
if(vis[i]) printf("%d ",&i-n);
puts("");
printf("%d\n",sum-maxflow);
return 0;
}