记录编号	92855	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-03-23 10:50:47	内存使用	0.31 MiB

#include<algorithm>
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>

using namespace std;

const int MAXN=100+10;
const int MAXP=2*MAXN;
const int INF=10000000; 

int M,N;

struct edge{
	int from,to,cap,flow;
};

struct dinic{
	vector<edge> edges;
	vector<int> G[MAXP];
	int s,t;int n,m;
	int cur[MAXP],d[MAXP];
	
	void init(){
		s=t=n=m=0;
	}
	
	void add_edge(int from,int to,int cap){
		edges.push_back((edge){from,to,cap,0});
		edges.push_back((edge){to,from,0,0});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	bool inq[MAXP];
	int BFS(){
		queue<int> q;
		memset(inq,0,sizeof(inq));
		memset(d,0,sizeof(d));
		q.push(s);inq[s]=true;
		while(!q.empty()){
			int u=q.front();q.pop();
			//inq[u]=false;
			for(int i=0;i<G[u].size();i++){
				edge &e=edges[G[u][i]];
				if(e.to==0 || d[e.to]|| e.cap<=e.flow)continue;
				d[e.to]=d[u]+1;
				//if(!inq[e.to])
				q.push(e.to);
			}
		}
		return d[t];
	}
	
	int DFS(int u,int a){
		if(a<=0)return 0;
		if(u==t)return a;
		int flow=0;
		for(int &i=cur[u];i<G[u].size();i++){
			edge &e=edges[G[u][i]];
			int f=0;
			if(d[e.to]-d[u]==1){
				f=DFS(e.to,min(a,e.cap-e.flow));
				if(f<=0)continue;
				a-=f;
				e.flow+=f;
				edges[G[u][i]^1].flow-=f;
				flow+=f;
			}
			if(a==0)break;
		}
		return flow;
	}
	
	int max_flow(){
		int flow=0;
		while(BFS()){
			memset(cur,0,sizeof(cur));
			flow+=DFS(s,INF);
		}
		return flow;
	}
	
	bool yi[MAXN],shi[MAXN],vis[MAXP];
	
	void dfs(int u){
		if(vis[u])return ;
		vis[u]=true;
		if(u<=M)shi[u]=true;
		if(u>M)yi[u-M]=true;
		for(int i=0;i<G[u].size();i++){
			edge &e=edges[G[u][i]];
			if(e.cap<=e.flow)continue;
			if(e.to!=0 && e.to!=t && !vis[e.to])dfs(e.to);
		}
	}
	
	void out_ans(){
		memset(yi,0,sizeof(yi));
		memset(shi,0,sizeof(shi));
		memset(vis,0,sizeof(vis));
		dfs(0);
		for(int i=1;i<MAXN;i++){
			if(shi[i])printf("%d ",i);
		}
		printf("\n");
		for(int i=1;i<MAXN;i++){
			if(yi[i])printf("%d ",i);
		}
		printf("\n");
	}
	
	void test(){
		for(int i=0;i<edges.size();i++){
			edge &e=edges[i];
			printf("e.from:%d e.to:%d e.cap:%d e.flow:%d",e.from,e.to,e.cap,e.flow);
			if(e.flow>e.cap)printf("=====================\n");
			else printf("\n");
		}
	}
}solver;

bool get_int(int &x){
	x=0;
	char ch=getchar();
	//printf("test\n");
	while(!(ch>='0' && ch<='9'))ch=getchar();
	while(ch>='0' && ch<='9'){
		x*=10;x+=ch-'0';
		ch=getchar();
	}
	//printf("test:%d\n",x);
	if(int(ch)==13)return true;
	else return false;
}

int read_and_build(){
	int m,n;//s=0 t=m+n 1-m实验 m+1-m+n仪器 
	scanf("%d %d",&m,&n);
	M=m;N=n;
	int s=0,t=m+n+1,nn=t+1;
	solver.s=s;solver.t=t;solver.n=nn;

	int sum=0;
	for(int i=1;i<=m;i++){
		int baoc=0;
		get_int(baoc);
		sum+=baoc;
		solver.add_edge(0,i,baoc);
		bool end=false;
		while(true){
			end=get_int(baoc);
			solver.add_edge(i,baoc+m,INF);
			if(end)break;
		}
	}
	//printf("test\n");
	//return 0;
	for(int i=m+1;i<=m+n;i++){
		int fei=0;
		get_int(fei);
		solver.add_edge(i,t,fei);
	}
	return sum;
}

void work(){
	//m 实验数 
	//n 仪器数
	int m,n,s,t;
	int sum=read_and_build();//正权和 

	int ans=solver.max_flow();
	//solver.test();
	ans=sum-ans;
	
	solver.out_ans();
	
	printf("%d",ans);
}

void open(){
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
}

void test(){
	for(int i=0;i<=15;i++){
		char c=getchar();
		printf("===%d %c===\n",int(c),c);
	}
}
int main(){
	open();
	//test();return 0;
	work();
	return 0; 
}