Cogs 727. [网络流24题] 太空飞行计划(最大权闭合子图)

[网络流24题] 太空飞行计划 ★★☆ 输入文件：shuttle.in 输出文件：shuttle.out 简单对比 时间限制：1 s 内存限制：128 MB 【问题描述】 W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em}，和进行这些实验需要使用的全部仪器的集合I={ I1, I2,…,In }。实验Ej 需要用到的仪器是I的子集Rj∈I。配置仪器Ik 的费用为ck 美元。实验Ej 的赞助商已同意为该实验结果支付pj 美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。 【编程任务】 对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。 【数据输入】 第1行有2个正整数m和n(m,n <= 100)。m是实验数，n是仪器数。接下来的m行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。 【结果输出】 第1行是实验编号；第2行是仪器编号；最后一行是净收益。 【输入文件示例】shuttle.in 2 3 10 1 2 25 2 3 5 6 7 【输出文件示例】shuttle.out 1 2 1 2 3 17 /* 最大权闭合子图的一般姿势. 这题要输出方案. 但是自己yy的输出姿势不对没想明白... 觉得可能是残余网络不理想,有反向弧啥的. 但是我们通过反向弧总能找到方案. */ #include<iostream> #include<cstdio> #include<queue> #define MAXN 210 #define INF 1e9 using namespace std; int n,m,S,T,ans,cut=1,dis[MAXN],head[MAXN],c[MAXN],p[MAXN]; queue<int>q; bool b[MAXN]; struct data{int u,v,next,c;}e[MAXN*MAXN*6]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } void add(int u,int v,int c) { e[++cut].u=u;e[cut].v=v;e[cut].c=c;e[cut].next=head[u];head[u]=cut; e[++cut].u=v;e[cut].v=u;e[cut].c=0;e[cut].next=head[v];head[v]=cut; } bool bfs() { for(int i=S;i<=T;i++) dis[i]=-1;dis[S]=0; q.push(S); while(!q.empty()) { int u=q.front();q.pop();b[u]=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]==-1&&e[i].c) { dis[v]=dis[u]+1; q.push(v); } } } return dis[T]!=-1; } int dfs(int u,int y) { if(u==T) return y; int rest=0; for(int i=head[u];i&&rest<y;i=e[i].next) { int v=e[i].v; if(dis[v]==dis[u]+1&&e[i].c) { int x=dfs(v,min(y-rest,e[i].c)); e[i].c-=x; e[i^1].c+=x; rest+=x; } } if(!rest) dis[u]=-1; return rest; } void slove(int u) { for(int i=head[u];i;i=e[i].next) if(e[i].c&&!b[e[i].v]) b[e[i].v]=true,slove(e[i].v); return ; } void dinic() { while(bfs()) ans-=dfs(S,INF); slove(S); /*for(int i=head[S];i;i=e[i].next) if(e[i].c) b[e[i].v]=true;*/ for(int i=1;i<=n;i++) if(b[i]) printf("%d ",i),b[i]=false; printf("\n"); /*for(int i=head[T];i;i=e[i].next) if(e[i].c) b[e[i].v-n]=true;*/ for(int i=n+1;i<=n+m;i++) if(b[i]) printf("%d ",i-n); printf("\n"); } int main() { freopen("shuttle.in","r",stdin); freopen("shuttle.out","w",stdout); int x,t=1;char ch; n=read(),m=read();S=0,T=n+m+1; for(int i=1;i<=n;i++) { scanf("%d",&x),add(S,i,x),ans+=x; x=0;ch=getchar(); while(ch!='\n') { if(ch>='0'&&ch<='9') x=x*10+ch-48; else if(x) add(i,x+n,INF),x=0; ch=getchar(); } if(x) add(i,x+n,INF); } for(int i=1;i<=m;i++) p[i]=read(); for(int i=1;i<=m;i++) add(i+n,T,p[i]); dinic(); printf("%d",ans); return 0; }