记录编号	194767	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	四季木哥	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-10-17 11:10:16	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define N 250
using namespace std;

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

int m,n;

vector<EDGE> edges;
vector<int> G[N];
bool vis[N];
int cur[N],d[N];
int s,t;

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});
	int siz=edges.size();
	G[from].push_back(siz-2);
	G[to].push_back(siz-1);    
}

bool BFS(){
	memset(vis,0,sizeof(vis));
	memset(d,0,sizeof(d));
	queue<int> q;
	q.push(s); 
	vis[s]=1;
	while(!q.empty()){
		int x=q.front();	
		q.pop();
		for(int i=0;i<G[x].size();i++){
			EDGE e=edges[G[x][i]];
			if(!vis[e.to]&&e.cap>e.flow){
				q.push(e.to);
				vis[e.to]=1; 	
				d[e.to]=d[x]+1;
			}
		}
	}
	return vis[t];
}

int DFS(int x,int rest){
	if(x==t||rest==0) return rest;
	int flow=0,f;
	for(int& i=cur[x];i<G[x].size();i++){
		EDGE& e=edges[G[x][i]];	
		if(d[x]+1==d[e.to]){
			f=DFS(e.to,min(rest,e.cap-e.flow));
			if(f>0){
				e.flow+=f;
				edges[G[x][i]^1].cap+=f;
				flow+=f;
				rest-=f;
				if(rest==0) return flow;
			}
		}
	}
	return flow;
}

int Maxflow(){
	int flow=0;
	while(BFS()){
		memset(cur,0,sizeof(cur));
		flow+=DFS(s,INF);
	}
	return flow;
}

int main(){
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	cin>>m>>n;
	int p,x;
	char y;
	s=0,t=m+n+1;
	int sum=0;
	for(int i=1;i<=m;i++){
		cin>>p;
		sum+=p;
		Add_Edge(s,i,p);
		while(scanf("%d%c",&x,&y)){
			Add_Edge(i,x+m,INF);
			if(y=='\r') break;
		}
	}
	for(int i=1;i<=n;i++){
		cin>>p;
		Add_Edge(i+m,t,p);
	}
	int ans=sum-Maxflow();
	for(int i=1;i<=m;i++)
		if(vis[i]) cout<<i<<" ";
	cout<<endl;
	for(int i=m+1;i<=m+n;i++)
		if(vis[i]) cout<<i-m<<" ";
	cout<<endl;
	cout<<ans;
return 0;
}