记录编号	417904	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-06-28 16:20:22	内存使用	0.82 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

namespace IO{
    inline char getc(void);
    inline int in(void);
    inline void write(void);
    inline void write(int x);
    inline void write_all(void);
    
    char ops[1 << 18], *opt = ops, *const opt_end = ops + (1 << 18);
    char *num = new char[20];

    inline char getc(void){
        static char buf[1 << 18], *fs, *ft;
        return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
    }

    inline int in(void){
        register int res = 0;
        register char tmp = getc();
        while(!isdigit(tmp)) tmp = getc();
        while(isdigit(tmp))
            res = (res + (res << 2) << 1) + (tmp ^ 48),
            tmp = getc();
        return res;
    }

    inline int get_line(int *s){ 
        register char tmp = getc();
        register int res = 0;
        register int cnt = 0;

        while(!isdigit(tmp)) tmp = getc();
        while(isdigit(tmp))
            res = (res + (res << 2) << 1) + (tmp ^ 48),
            tmp = getc();
        *(s++) = res;
        ++cnt;

        while(tmp ^ '\n' && tmp ^ '\r'){ 
            while(!isdigit(tmp) && tmp ^ '\n' && tmp ^ '\r') tmp = getc();
            if(tmp == '\n' || tmp == '\r') return cnt;
            res = 0;
            while(isdigit(tmp))
                res = (res + (res << 2) << 1) + (tmp ^ 48),
                tmp = getc();
            *(s++) = res;
            ++cnt;
        }
        return cnt;
    }

    inline void write(int x){
        if(x < 0){ 
            x = -x;
            *(opt++) = '-';
            if(opt == opt_end) write_all();
        }

        do{
            *(++num) = (x % 10) | 0x30;
            x /= 10;
        }while(x);

        while(*num){
            *(opt++) = *(num--);
            if(opt == opt_end) write_all();
        }

        *(opt++) = ' ';
        if(opt == opt_end) write_all();
        return ;
    }

    inline void write(void){
        *(opt++) = '\n';
        if(opt == opt_end) write_all();
        return ;
    }

    inline void write_all(void){
        fwrite(ops, 1, opt - ops, stdout);
        opt = ops;
        return ;
    }
}
using IO::in;
using IO::get_line;
using IO::write;
using IO::write_all;

const int MAXN = 1e3 + 10;
const int INF = 0x7fffffff;

struct EDGE{
    int to, cap;
    EDGE *ne, *rcap;

    EDGE(){;}
    EDGE(int _to, EDGE *_ne, int _cap){
        to = _to, ne = _ne, cap = _cap;
    }
};

inline void add_edge(int fr, int to, int cap);
inline bool bfs(void);
int dfs(int u, int Min);

EDGE *head[MAXN];
int bfn[MAXN];
int S, T, max_flow;
int N, M, tot;
int *const tmp = new int[110];

int main(){ 
#ifndef LOCAL
    freopen("shuttle.in", "r", stdin);
    freopen("shuttle.out", "w", stdout);
#endif
    N = in(), M = in();
    S = 0, T = N + M + 1;
    for(int i = 1, cnt; i <= N; ++i){ 
        cnt = get_line(tmp);
        tot += *tmp;
        add_edge(S, i, tmp[0]);
        for(int j = 1; j < cnt; ++j){ 
            add_edge(i, tmp[j] + N, INF);
        }
    }
    delete []tmp;

    for(int i = N + 1; i < T; ++i){ 
        add_edge(i, T, in());
    }
    int tmp;
    while(bfs()){ 
        while((tmp = dfs(S, INF))) max_flow += tmp;
    }

    for(int i = 1; i <= N; ++i) if(bfn[i] > 0) write(i);
    write();
    for(int i = N + 1; i < T; ++i) if(bfn[i] > 0) write(i - N);
    write();
    write(tot - max_flow);

    write_all();
    return 0;
}

inline void add_edge(int fr, int to, int cap){
    head[fr] = new EDGE(to, head[fr], cap);
    head[to] = new EDGE(fr, head[to], 0);
    head[fr]->rcap = head[to];
    head[to]->rcap = head[fr];
    return ;
}

inline bool bfs(void){
    static queue<int> que;
    static int u, v;

    memset(bfn, 0x00, sizeof(bfn));
    while(!que.empty()) que.pop();

    bfn[S] = 1;
    que.push(S);

    while(!que.empty()){
        u = que.front();
        que.pop();
        if(u == T) return true;

        for(register EDGE *e = head[u]; e; e = e->ne){ 
            if(!e->cap || bfn[v = e->to]) continue;
            bfn[v] = bfn[u] + 1;
            que.push(v);
        }
    }

    return false;
}

int dfs(int u, int Min){ 
    if(u == T) return Min;
    register int sum;
    for(register EDGE *e = head[u]; e; e = e->ne){ 
        if(e->cap && bfn[e->to] == bfn[u] + 1 && (sum = dfs(e->to, min(Min, e->cap)))){ 
            e->cap -= sum;
            e->rcap->cap += sum;
            return sum;
        }
    }
    return 0;
}