记录编号	141989	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	lky	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-12-05 20:53:08	内存使用	0.67 MiB

/*
	Problem : shuttle		
	Author: Soap
	Date: 05/12/14 19:40
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
using namespace std;
#define rep(frep,ss,tt) for (frep=ss;frep<=tt;++frep)
#define drep(frep,tt,ss) for (frep=tt;frep>=ss;--frep)
#define INF 0x3f3f3f3f
#define N 210
struct edge{
	int to,next,cap,op;
	void build(int a,int b,int c,int d){
		to=a,next=b,cap=c,op=d;
	}
}e[25001];
int tot,head[N],S,T,nodes,dep[N],gap[N],m,n,money,cost;
bool vis[N];

void add(int u,int v,int c){
	++tot,e[tot].build(v,head[u],c,tot+1),head[u]=tot;
	++tot,e[tot].build(u,head[v],0,tot-1),head[v]=tot;
}
int SAP(int now,int delta){
    if (now==T) return delta;
    int mindis=nodes,sum=0;
    for (int j=head[now];j;j=e[j].next){
        if (e[j].cap>0 && dep[e[j].to]+1==dep[now]){
            int save=SAP(e[j].to,min(delta-sum,e[j].cap));
            sum+=save;
            e[j].cap-=save;
            e[e[j].op].cap+=save;
            if (sum==delta || dep[S]>=nodes) return sum;
            }
        if (e[j].cap>0) mindis=min(mindis,dep[e[j].to]);
    }
    if (!sum){
        if (!--gap[dep[now]]) dep[S]=nodes;
          else ++gap[dep[now]=mindis+1];
        }
    return sum;
}

void dfs(int now){
  vis[now]=1;
  for (int j=head[now],v=e[j].to;j;j=e[j].next,v=e[j].to)
    if (e[j].cap>0 && !vis[v]) dfs(v);
}

int main(){
  freopen("shuttle.in","r",stdin);
  freopen("shuttle.out","w",stdout);
  scanf("%d%d",&m,&n);
  int i,x; char ch;
  S=0; T=m+n+1; nodes=T+1;
  rep(i,1,m){
  	scanf("%d",&x);
  	add(S,i,x);
  	money+=x;
  	while (scanf("%d%c",&x,&ch)){
		add(i,m+x,INF);
		if (ch=='\r') break;
	}
  }
  rep(i,1,n) scanf("%d",&x),add(m+i,T,x);
  gap[0]=nodes;
  while (dep[S]<nodes) cost+=SAP(S,INF);
  dfs(S);
  rep(i,1,m) if (vis[i]) printf("%d ",i);
  puts("");
  rep(i,1,n) if (vis[i+m]) printf("%d ",i);
  puts("");
  printf("%d\n",money-cost);
  fclose(stdin); fclose(stdout);
  return 0;
}