记录编号	417385	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-06-25 13:45:34	内存使用	0.77 MiB

# include <bits/stdc++.h>
# define INF 0x7fffffff
# define MAXN 103
using namespace std;
inline char getc() { 
    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 gn() { 
    int k = 0, f = 1;
    char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = 0;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}

struct edge { 
    int fr, to, w, ne;
    edge(){ne = -1;}
    edge(int x, int y, int k, int z) { 
        fr = x, to = y, w = k, ne = z;
    }
}e[MAXN << 7];

int cnt, head[MAXN << 1];

inline void addedge(int fr, int to, int w) { 
    e[cnt] = edge(fr, to, w, head[fr]), head[fr] = cnt++;
    e[cnt] = edge(to, fr, 0, head[to]), head[to] = cnt++;
}

int n, m, S, T, pre[MAXN << 1], sum;

inline bool bfs() { 
    memset(pre, -1, sizeof(pre));
    queue <int> q;
    q.push(S);
    pre[S] = INF;
    while(!q.empty()) { 
        int u = q.front();
        q.pop();
        for(int i = head[u]; ~i; i = e[i].ne) { 
            int v = e[i].to;
            if(~pre[v] || !e[i].w) continue;
            pre[v] = i;
            q.push(v);
        }
    }
    return ~pre[T];
}

inline int get_flow() { 
    int ans = INF, now = pre[T];
    while(now ^ INF) { 
        ans = min(ans, e[now].w);
        now = pre[e[now].fr];
    }
    now = pre[T];
    while(now ^ INF) { 
        e[now].w -= ans;
        e[now ^ 1].w += ans;
        now = pre[e[now].fr];
    }
    return ans;
}

vector <int> I[MAXN];

int main() { 
# ifndef LOCAL
    freopen("shuttle.in", "r", stdin);
    freopen("shuttle.out", "w", stdout);
# else 
    freopen("in", "r", stdin);
# endif
    memset(head, -1, sizeof(head));
    m = gn(), n = gn();
    S = m + n + 1;
    T = S + 1;
    char c;
    int k;
    for(int i = 1; i <= m; i++) { 
        int temp = gn();
        sum += temp;
        addedge(S, i, temp);
        c = getc();
        k = 0;
        while(c != '\r') { 
            for(; !isdigit(c); c = getc());
            for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
            I[i].push_back(k);
            k = 0;
        }
    }
    for(int i = 1; i <= n; i++) { 
        addedge(m + i, T, gn());
    }
    for(int i = 1; i <= m; i++) { 
        for(unsigned int j = 0; j < I[i].size(); j++) { 
            addedge(i, m + I[i][j], INF);
        }
    }
    int ans = 0;
    while(bfs()) { 
        ans += get_flow();
    }
    for(int i = 1; i <= m; i++) if(~pre[i]) printf("%d ", i);
    printf("\n");
    for(int i = m + 1; i <= m + n; i++) if(~pre[i]) printf("%d ", i - m);
    printf("\n");
    printf("%d\n", sum - ans);
}