记录编号	474951	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	雨季	是否通过	通过
代码语言	C++	运行时间	0.175 s
提交时间	2017-11-13 16:53:12	内存使用	0.86 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
#define N 400
#define M 80000

int n,m;
int S,T;
int TOT,ans;

struct node {
	int v,c,nex;
}e[M];
int tot=1,h[N],use[N];
void add(int u,int v,int c) {
	e[++tot].v=v;
	e[tot].c=c;
	e[tot].nex=h[u];
	h[u]=tot;
}
int dis[N];
bool vis[N];
queue<int>q;
bool bfs() {
	while(!q.empty()) q.pop();
    for(int i=S;i<=T;++i) vis[i]=0,dis[i]=-1;
    q.push(S);
    vis[S]=1;
    dis[S]=0;
    int x,xx;
    while(!q.empty()) {
        x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].nex) {
            xx=e[i].v;
            if(e[i].c&&!vis[xx]) {
                vis[xx]=1;
                dis[xx]=dis[x]+1;
                q.push(xx);
            }
        }
        if(vis[T]) return 1;
    }
    return 0;
}
int dfs(int x,int want) {
    if(x==T||!want) return want;
    int xx,get=0,f=0;
    for(int i=use[x];i;i=e[i].nex) {
        xx=e[i].v;
        if(dis[xx]==dis[x]+1) {
            f=dfs(xx,min(e[i].c,want));
            if(!f) continue;
            e[i].c-=f;
            e[i^1].c+=f;
            want-=f;
            get+=f;
            use[x]=i;
            if(want==0) break;
        }
    }
    return get;
}

// 很显然为最大权闭合子图，ans=所有正权和-最小割，最小割=最大流
int main() 
{
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	scanf("%d%d",&m,&n);
	int p,x;
	S=0,T=n+m+1;
	char ch;
	for(int i=1;i<=m;++i) {
		scanf("%d",&p);
		TOT+=p;
		add(S,i,p);
		add(i,S,0);
		while((ch=getchar())!='\n'&&ch!='\r') {
			scanf("%d",&x);
			add(i,x+m,1e9);
			add(x+m,i,0);
		}
	} 
	for(int i=1;i<=n;++i) {
		scanf("%d",&p);
		add(i+m,T,p);
		add(T,i+m,0);
	}//cout<<"wwwwwww "<<TOT<<endl;
	while(bfs()) {//cout<<"www"<<endl;
		for(int i=S;i<=T;++i) use[i]=h[i];
		ans+=dfs(S,1e9);
	}//cout<<ans<<endl;
	for(int i=1;i<=m;++i) {
		if(dis[i]!=-1) printf("%d ",i); 
	} putchar('\n');
	for(int i=m+1;i<=m+n;++i) {
		if(dis[i]!=-1) printf("%d ",i-m);
	} putchar('\n');
	printf("%d\n",TOT-ans);
	return 0;
}