记录编号	367641	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-01-31 21:50:10	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=510,INF=0x7fffffff/2;
class Edge{
public:
	int from,to,cap,flow;
};
class Dinic{
public:
	int S,T;
	vector<Edge> edges;
	vector<int> c[SIZEN];
	void addedge(int from,int to,int cap){
		//cout<<from<<" "<<to<<" "<<cap<<endl;
		edges.push_back((Edge){from,to,cap,0});
		edges.push_back((Edge){to,from,0,0});
		int tot=edges.size()-2;
		c[from].push_back(tot);
		c[to].push_back(tot+1);
	}
	int dep[SIZEN];
	bool vis[SIZEN];
	bool BFS(void){
		queue<int> Q;
		memset(vis,0,sizeof(vis));
		memset(dep,0,sizeof(dep));
		dep[S]=0;Q.push(S);vis[S]=true;
		while(!Q.empty()){
			int x=Q.front();Q.pop();
			for(int i=0;i<c[x].size();i++){
				Edge &e = edges[c[x][i]];
				if(!vis[e.to]&&e.cap>e.flow){
					dep[e.to]=dep[x]+1;vis[e.to]=true;Q.push(e.to);
				}
			}
		}
		return vis[T];
	}
	int cur[SIZEN];
	int DFS(int x,int a){
		//cout<<x<<" "<<a<<endl;
		if(x==T||!a) return a;
		int ret=0;
		for(int &i=cur[x];i<c[x].size();i++){
			Edge &e=edges[c[x][i]];
			if(dep[e.to]==dep[x]+1){
				//if(e.cap-e.flow<0) cout<<e.cap<<" "<<e.flow<<endl;
				int cf=DFS(e.to,min(a,e.cap-e.flow));
				if(cf){
					//if(a-cf<0) cout<<a<<" "<<e.cap-e.flow<<" "<<min(a,e.cap-e.flow)<<" "<<cf<<" "<<ret<<endl;
					a-=cf;
					ret+=cf;
					e.flow+=cf;
					edges[c[x][i]^1].flow-=cf;
				}
				if(!a) break;
			}
		}
		if(!ret) dep[x]=-1;
		return ret;
	}
	int solve(void){
		int ret=0;
		while(BFS()){
			memset(cur,0,sizeof(cur));
			ret+=DFS(S,INF);
		}
		return ret;
	}
}D;
void work(void){
	int ans=0;
	int m,n;//m个实验,n个仪器
	scanf("%d%d\n",&m,&n);
	D.S=0,D.T=n+m+1;
	char buffer[100];
	int x;
	for(int i=1;i<=m;i++){
		//cout<<buffer<<endl;
		scanf("%d",&x);//回报
		ans+=x;
		gets(buffer);
		char *p=buffer; 
		D.addedge(D.S,i,x); 
		while(true){
			while((*p)&&!isdigit(*p)) p++;
			if(sscanf(p,"%d",&x)==EOF) break;
			D.addedge(i,m+x,INF);
			while(isdigit(*p)) p++;
		}
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		D.addedge(m+i,D.T,x);
	}
	//cout<<ans<<endl;
	ans-=D.solve();
	D.BFS();
	for(int i=1;i<=m;i++){
		if(D.vis[i]) printf("%d ",i);
	}
	printf("\n");
	for(int i=1;i<=n;i++){
		if(D.vis[m+i]) printf("%d ",i);
	}
	printf("\n%d\n",ans);
}
int main(){
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	work();
	return 0;
}