[网络流24题] 2. 太空飞行计划问题 解题报告

太空飞行计划问题

题意

有 (m) 组实验, (n) 个器材,

每个实验需要若干个器材, 可以获得一定收益, 每个器材有一定的费用,

求最大净收益 (总收益 - 总费用), 并输出方案.

思路

将每个器材连向 (S), 边权为器材的费用,

将每个实验连向 (T), 边权为实验的收益,

每个器材向需要它的实验连边, 边权为 (inf),

跑最小割就行了.

需要注意的是, 最后输出方案, 判断每个器材是否被选中时, 不能单纯地判断 (S) 连向它的边权是否为 (0),

因为就算边权为 (0), (S) 还是能够通过其他路径增广它,

所以应该判断 (Dinic) 算法最后一次 (bfs) 时有没有经过它, 如果没有经过, 就表示它被选中了.

代码

#include<bits/stdc++.h>
#define pb push_back
#define sz size
using namespace std;
const int _=100+7;
const int __=20400+7;
const int inf=0x3f3f3f3f;
int n,m,S,T,d[_],max_flow,ans;
int lst[_],nxt[__],to[__],c[__],tot=1;
char tools[10000];
queue<int> q;
vector<int> nd[_];
void add(int x,int y,int w){ nxt[++tot]=lst[x]; to[tot]=y; c[tot]=w; lst[x]=tot; }
void read(){
  cin>>m>>n; m+=n;
  S=m+1; T=m+2;
  int x;
  for(int i=n+1;i<=m;i++){
    scanf("%d",&x);
    ans+=x;
    add(i,T,x);
    add(T,i,0);
    memset(tools,0,sizeof tools);
    cin.getline(tools,10000);
    int ulen=0,tool;
    while (sscanf(tools+ulen,"%d",&tool)==1)
      {
	if (tool==0) 
	  ulen++;
	else {
	  add(tool,i,inf);
	  add(i,tool,0);
	  nd[i-n].pb(tool);
	  while (tool) {
	    tool/=10;
	    ulen++;
	  }
	}
	ulen++;
      }
  }
  for(int i=1;i<=n;i++){
    scanf("%d",&x);
    add(S,i,x);
    add(i,S,0);
  }
}
bool bfs(){
  for(int i=1;i<=T;i++) d[i]=0;
  while(!q.empty()) q.pop();
  q.push(S); d[S]=1;
  while(!q.empty()){
    int u=q.front(); q.pop();
    for(int i=lst[u];i;i=nxt[i]){
      int v=to[i];
      if(d[v]||!c[i]) continue;
      d[v]=d[u]+1;
      if(v==T) return 1;
      q.push(v);
    }
  }
  return 0;
}
int dfs(int u,int flow){
  if(u==T) return flow;
  int rest=flow;
  for(int i=lst[u];i;i=nxt[i]){
    int v=to[i];
    if(d[v]!=d[u]+1||!c[i]) continue;
    int cost=dfs(v,min(rest,c[i]));
    c[i]-=cost; c[i^1]+=cost;
    rest-=cost;
  }
  return flow-rest;
}
void Dinic(){
  int flow;
  while(bfs())
    do{
      flow=dfs(S,inf);
      max_flow+=flow;
    }while(flow);
  ans-=max_flow;
}
void print(){
  for(int u=1;u<=m-n;u++){
    bool flag=1;
    for(int i=0;i<(int)nd[u].sz();i++)
      if(d[nd[u][i]]){ flag=0; break; }
    if(flag) printf("%d ",u);
  }
  putchar('
');
  for(int i=1;i<=n;i++)
    if(!d[i]) printf("%d ",i);
  putchar('
');
  printf("%d
",ans);
}
int main(){
  //freopen("x.in","r",stdin);
  read();
  Dinic();
  print();
  return 0;
}