题目链接
https://www.luogu.com.cn/problem/P2762
题解
引入一个最大权闭合子图的概念。
一个图的闭合子图 \(G\)，满足 \(\forall u \in G\)，\(u\) 的所有出边连向的点都属于 \(G\)。
如果给图上的点标记点权，则点权和最大的闭合子图称为最大权闭合子图。
对于本题，如果实验 \(i\) 需要仪器 \(j\)，则连 \(i \to j\) 的边，容易看出，我们选择的图需要是原图的一个闭合子图。
如果我们给每个点标上点权（收益为正数，支出为负数），则目标就变成了求原图的最大权闭合子图。
求一个图的最大权闭合子图可以用网络流解决。
我们将图 \(G\) 上的点分为两部分 \(S,T\)，其中 \(\forall u \in S\)，都有 \(a_u \geq 0\)（\(a_u\) 为 \(u\) 的点权），\(\forall u \in T\)，都有 \(a_u < 0\)。
从 \(s\) 向 \(S\) 的所有点连流量为点权的边，从 \(T\) 的所有点向 \(t\) 连流量为点权的相反数的边。
对于原图中已经有的边 \(u \to v\)，则连 \(u \to v\)，流量为 \(\infty\) 的边。
则一个图的最大权闭合子图的权值和等于所有正权点的权值和减去网络流的最小割。
这里的最小割的意义是：如果割掉了 \(s\) 向 \(S\) 中的点的边，则表示不选择这个点；如果割掉了 \(T\) 中的点向 \(t\) 的边，则表示选择这个点。
正确性证明
先证明这个构造方案是合法的。
首先因为 \(S\) 中的点和 \(T\) 中的点连的所有边的权值均为 \(\infty\)，所以最小割一定不会割掉这些边。
如果选择了一个正权点 \(u\)，为了确保整个图必须是闭合子图，则必须选择 \(u\) 的所有后继点。
设 \(u\) 的后继点为 \(v\)。
- 若 \(a_v < 0\)，则根据上面最小割的意义，\(v \to t\) 的边将会被割掉。
- 若 \(a_v \geq 0\)，则割掉 \(s \to v\) 的边不影响图的连通性，所以这条边不会被割掉。
因此这种建模方法确保了 \(u\) 的所有后继都被选择。
在上面的讨论中，我们只考虑了先选择一个正权点的情况。
但显然先选择一个负权点是不优的。因为我们可以直接选这个负权点后继的正权点就可以了。
最优性证明比较显然，这里略去。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
int v,w,next;
}e[100005];
int n,m,s,t,cnt=1;
int head[105],dep[105],vis[105],cur[105];
vector<int> res1,res2;
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
bool bfs()
{
queue<int> q;
memset(dep,INF,sizeof(dep));
memset(vis,0,sizeof(vis));
memcpy(cur,head,sizeof(head));
dep[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int p=q.front();
q.pop();
vis[p]=0;
for(int i=head[p];i;i=e[i].next)
if(dep[e[i].v]>dep[p]+1&&e[i].w)
{
dep[e[i].v]=dep[p]+1;
if(!vis[e[i].v])
{
vis[e[i].v]=1;
q.push(e[i].v);
}
}
}
if(dep[t]==INF)return 0;
return 1;
}
int dfs(int p,int w)
{
if(p==t)return w;
int used=0;
for(int i=cur[p];i;i=e[i].next)
{
cur[p]=i;
if(dep[e[i].v]==dep[p]+1&&e[i].w)
{
int flow=dfs(e[i].v,min(w-used,e[i].w));
if(flow)
{
used+=flow;
e[i].w-=flow;
e[i^1].w+=flow;
if(used==w)break;
}
}
}
return used;
}
void dfs(int x)
{
vis[x]=1;
if(x==t)return;
if(x<=n)res1.push_back(x);
else if(x!=s)res2.push_back(x-n);
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].v;
if(!vis[v]&&e[i].w)dfs(v);
}
}
int main()
{
int ans=0;
cin>>n>>m;
s=n+m+1,t=n+m+2;
for(int i=1;i<=n;i++)
{
int c;
cin>>c;
ans+=c;
addedge(s,i,c),addedge(i,s,0);
string str;
getline(cin,str);
stringstream ss(str);
int x;
while(ss>>x)
addedge(i,x+n,INF),addedge(x+n,i,0);
}
for(int i=1;i<=m;i++)
{
int c;
cin>>c;
addedge(i+n,t,c),addedge(t,i+n,0);
}
while(bfs())
ans-=dfs(s,INF);
dfs(s);
sort(res1.begin(),res1.end());
sort(res2.begin(),res2.end());
for(auto x:res1)
cout<<x<<' ';
cout<<endl;
for(auto x:res2)
cout<<x<<' ';
cout<<endl;
cout<<ans<<endl;
return 0;
}