网络流24题（2）
二、太空飞行计划问题
题目描述
\(W\) 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 \(E = \{ E_1, E_2, ...,E_m\}，\)和进行这些实验需要使用的全部仪器的集合 \(I=\{I_1,I_2,⋯,I_n\}\)。实验 \(E_j\) 需要用到的仪器是 \(I\) 的子集 \(R_j \subseteq I\)。
配置仪器 \(I_k\) 的费用为 \(c_k\) 美元。实验 \(E_j\) 的赞助商已同意为该实验结果支付 \(p_j\) 美元。\(W\) 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。
输入格式
第 \(1\) 行有 \(2\) 个正整数 \(m\) 和 \(n\)。\(m\) 是实验数，\(n\) 是仪器数。接下来的 \(m\) 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的 \(n\) 个数是配置每个仪器的费用。
\(1<=n,m<=50\)
输出格式
第 \(1\) 行是实验编号，第 \(2\) 行是仪器编号，最后一行是净收益。
题解
简述模型：
最大权闭合图问题，可以转化为最小割问题，最小割所产生的两个集合中，其源点\(S\)所在集合(除去\(S\))为最大权闭合图，再变成最大流问题。
建图：
将所有实验看作一个顶点集合 \(X\)，每个设备看作顶点集合\(Y\)，构建二分图\(G\)。并设置超级源点\(s\)和超级汇点\(t\)。
1.\(s\)向\(X\)中的每个顶点连接一条容量为该点点权的有向边。
2.\(Y\)中每个顶点向\(t\)连接一条容量为该点点权的有向边
3.在原二分图上的每条有向边容量设置为无穷大。
证明模型的正确性：
(原自胡伯涛的论文《最小割模型在信息竞赛中的运用》)
什么是闭合图？
在一张图中，我们取一个点集合\(V\)，其中\(V\)中点所有的边所指的终点也在\(V\)中，这样的图称之为闭合图。
很显然，在该题中，如果做若干的实验，再取对应的仪器，这样构成的图一定是闭合图。所以我们取得的最大的闭合图就是我们要求的方案。
定义：简单割为图中\(s\)-\(t\)割满足割中的每条边都与源点\(s\)和汇点\(t\)关联。
定理1：最小割是简单割。
最小割最大为所有非无穷边的和，即最小割不包含容量为无穷的边。即最小割为简单割。
假设：
简单割\([S,T]\)将网络\(N\)的点集\(V_N\)划分为点集\(S\)及其补集\(T\)，满足\(s\)在\(S\)中，\(t\)在\(T\)中。
设闭合图\(V_1\)，它在\(V\)中的补集为\(V_2\)，\(V^+\)为\(V\)中点权为正的点集，\(V^-\)为\(V\)中点权为负的点集，在其他集合中也是如此。
定理2：简单割\([S,T]\)与图\(G\)的闭合图\(V_1\)存在一个一一对应关系：\(V_1\cup\{s\} = S\)。
证明：
（1）闭合图对应简单割：
已知：\(S= V_1\cup\{s\},T = V_2\cup\{t\}\)，求证\([S,T]\)为简单割。
假如有一条边\(<u,v>\)，从\(V_1\)指向\(V_2\)，使得\([S,T]\)含不与\(s\)或者\(t\)相关的边。
此时，\(V_1\)有一个后继不在闭合图内，矛盾。
（2）简单割对应闭合图：
证明\(V_1=S\)-\(\{s\}\)是闭合图。\(V_1\)任意引出一条边，因为简单割不存在一条正无穷边所以，这条边的终点也在\(V_1\)中，符合闭合图定义。
定理3：“图S中所有点的权值和\(W\)” = “整个图中所有正权值之和\(tot\)” - “割集中所有边权值和\(C\)”
证明：
对于简单割：
割的容量\(C\)为连接到\(s\)的点的权值\(x_1\)加上连接到\(t\)的点的权值\(x_2\)，其中点\(s\)只与正点相连，点\(t\)只与负点相连。
\((1)C = x_1+x_2\)
对于闭合图：
闭合图的权和\(W\)为正权点的权的绝对值\(w_1\)和减去负权点的权的绝对值和\(w_2\)。
\((2)W = w_1-w_2\)
可以得到\(x_2 = w_2\)（闭合图中的负边一定连接到\(t\)上）
相加可得 \(C+W = x_1+w_1\)
\(x_1+w_1\)即为所有正数的权值和，命名为\(tot\)。
得\(W = tot-C\)。
代码：
跑出最小割\(C\),统计正数点权权值和\(tot\)，得出答案\(W\)
输出方案的解释源自洛谷红名大佬 huangzirui:
假如我们跑的是 Dinic 那么我们最后一次网络流（这一次网络流并没有起任何作用，只是确认了无更多残余流量可以退出了。）中所有被分到层的都一定被选上了。
没有更多残余流量其实意味着这个图已经被割成了两部分，一个实验如果有层数意味着它没有被割掉（被选上了），一个仪器如果有层数意味着它已经被割掉了（也是被选上了）。
于是只要在最后输出所有有层数的点就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=210;
const int maxm = 5e3+10;
ll level[maxn],head[2*maxm],cur[2*maxm],cnt;
ll n,m;
ll ss,ee;
struct Edge{ll to,nxt,w;}edge[2*maxm];
void init(){
cnt=0;
memset(head,-1,sizeof head);
}
void add(ll u,ll v,ll w){
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].nxt=head[u];
head[u]=cnt++;
}
void add2(ll u,ll v,ll w,bool op){//是否为有向图
add(u,v,w);
add(v,u,op?0:w);
}
bool bfs(ll s,ll t){//分层图
queue<ll>q;
memset(level,0,sizeof level);
level[s]=1;
q.push(s);
while(!q.empty()){
ll x=q.front();
q.pop();
if(x==t)return true;
for(ll u=head[x];~u;u=edge[u].nxt){
ll v=edge[u].to,w=edge[u].w;
if(!level[v]&&w){
level[v]=level[x]+1;
q.push(v);
}
}
}
return false;
}
ll dfs(ll u,ll maxf,ll t){
if(u==t)return maxf;
ll ret=0;
for(ll i=head[u];~i;i=edge[i].nxt){
ll v=edge[i].to;ll w=edge[i].w;
if(level[u]+1==level[v]&&w){
ll MIN=min(maxf-ret,w);
w=dfs(v,MIN,t);
edge[i].w-=w;
edge[i^1].w+=w;
ret+=w;
if(ret==maxf)break;
}
}
if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了
return ret;
}
ll Dinic(ll s,ll t){
ll ans=0;
while(bfs(s,t)) ans+=dfs(s,INF,t);
return ans;
}
int main(){
ios::sync_with_stdio(false);
init();
cin>>m>>n;
ll tot = 0;
char tools[10000];
for(ll i = 1;i <= m;++i){
ll x;cin>>x;
add2(0,i,x,true);
tot += x;
memset(tools,0,sizeof tools);
cin.getline(tools,10000);
int ulen=0,tool;
while (sscanf(tools+ulen,"%d",&tool)==1){//之前已经用scanf读完了赞助商同意支付该实验的费用
//tool是该实验所需仪器的其中一个
//这一行，你可以将读进来的编号进行储存、处理，如连边。
//cout<<tool<<endl;
add2(i,tool+m,INF,true);
if (tool==0)ulen++;
else {
while (tool) {
tool/=10;
ulen++;
}
}
ulen++;
}
}
for(ll i = 1;i <= n;++i){
ll x;cin>>x;
add2(i+m,n+m+1,x,true);
}
ll ans = Dinic(0,n+m+1);
for(ll i = 1;i <= m;i++) if(level[i]>0)cout<<i<<' ';
cout<<endl;
for(ll i = 1;i <= n;i++) if(level[i+m]>0)cout<<i<<' ';
cout<<endl<<tot-ans<<endl;
return 0;
}