记录编号	149188	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-02-20 14:48:27	内存使用	0.75 MiB

/****************************************\
* Author : ztx
* Title  : [cogs] 727. [网络流24题] 太空飞行计划
* ALG    : 网络流 最小割
* CMT    : 见黑书
* Time   :
\****************************************/

#include <cstdio>

typedef long long ll ;

int CH , NEG ;
template<typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#define  ENDL  -1234567
#define  ENDF  -12345678
#define  FALD  -123456789
#define  SUCS  1234567

template<typename TP>inline int read_plus(TP& ret) {
	ret = NEG = 0 ; while (CH=getchar() , CH<'!'&&CH!=EOF&&CH!='\n') ;
	if (CH == EOF) { ret = FALD ; return ENDF ; }
	else if (CH == '\n') { ret = FALD ; return ENDL ; }
	else if (CH == '-') NEG = true , CH = getchar() ;
	while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
	if (NEG) ret = -ret ;
	if (CH == '\n') return ENDL ;
	else if (CH == EOF) return ENDF ;
	return SUCS ;
}

#include <cstring>

#define  maxN  300LL
#define  maxM  20000LL
#define  infi  0x3f3f3f3fLL

struct FST { int to , next , flow ; } e[maxM<<1] ;
int star[maxN] , tote ;
inline void FST_init() { memset(star , 0 , sizeof star) ; tote = 1 ; }
inline void AddEdge(int u , int v , int cap) {
	e[++tote].to = v ; e[tote].flow = cap ; e[tote].next = star[u] ; star[u] = tote ;
	e[++tote].to = u ; e[tote].flow = 0 ; e[tote].next = star[v] ; star[v] = tote ;
}

#define  min(x,y) ((x)<(y)?(x):(y))
int N , S , T ;
int h[maxN] , vh[maxN] ;

int dfs(int u , int flowu) {
int p , tmp = h[u]+1 ;
int flow = 0 , flowv ;
	if (u == T) return flowu ;
	for (p = star[u] ; p ; p = e[p].next) {
		if (e[p].flow && (h[e[p].to]+1==h[u])) {
			flowv = dfs(e[p].to , min(flowu-flow , e[p].flow)) ;
			flow += flowv ; e[p].flow -= flowv ; e[p^1].flow += flowv ;
			if (flow==flowu || h[S]==N) return flow ;
		}
	}
	for (p = star[u] ; p ; p = e[p].next)
		if (e[p].flow) tmp = min(tmp , h[e[p].to]) ;
	if (--vh[h[u]] == 0) h[S] = N ;
	else ++ vh[h[u]=tmp+1] ;
	return flow ;
}

int SAP() {
	int ret = 0 ;
	memset(vh , 0 , sizeof vh) ;
	memset(h , 0 , sizeof h) ;
	vh[S] = N ;
	while (h[S] < N) ret += dfs(S , infi) ;
	return ret ;
}

int n , m , ans = 0 ;
bool vis[maxN] = {0} ;

void visit(int u) {
int v , p ;
	vis[u] = true ;
	for (p = star[u] ; p ; p = e[p].next)
    	if (v=e[p].to , e[p].flow>0 && !vis[v]) visit(v) ;
}

int main() {
int i , u , v , w ;
	#define READ
	#ifdef  READ
		freopen("shuttle.in" ,"r",stdin ) ;
		freopen("shuttle.out","w",stdout) ;
	#endif
	read(m) , read(n) ;
	S = n+m+1 , T = N = S+1 ;
	FST_init() ;
	for (u = 1 ; u <= m ; u ++ ) {
		read(w) , ans += w , AddEdge(S , u , w) ;
		while (1) {
			if (read_plus(v) == SUCS) {
				AddEdge(u , v+m , infi) ;
				continue ;
			} else {
				if (v != FALD) AddEdge(u , v+m , infi) ;
				break ;
			}
		}
	}
	for (i = 1 ; i <= n ; i ++ ) read(w) , AddEdge(i+m , T , w) ;
	ans -= SAP() ;
	visit(S) ;
	for (i = 1 ; i <= m ; i ++ ) if (vis[i]) printf("%d ", i) ;
	putchar('\n') ;
	for (i = m+1 ; i < S ; i ++ ) if (vis[i]) printf("%d ", i-m) ;
	printf("\n%d\n", ans) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}