Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- #define endl '\n'
- const int N = 1e2 + 10;
- const int INF = 0x3f3f3f3f;
- class Dinic {
- private:
- struct Edge {
- int from, to, cap, flow;
- Edge (int u, int v, int c, int f) :
- from(u), to(v), cap(c), flow(f){}
- };
- vector<Edge> edges;
- vector<int> g[N];
- int dep[N], cur[N];
- int n;
- public:
- void init (int _n) {
- n = _n;
- for (int i = 0; i <= n; i ++) {
- g[i].clear();
- }
- edges.clear();
- }
- void addEdge (int u, int v, int c) {
- edges.push_back({u, v, c, 0});
- edges.push_back({v, u, 0, 0});
- int m = edges.size();
- g[u].push_back(m - 2);
- g[v].push_back(m - 1);
- }
- int bfs (int s, int t) {
- queue<int> q;
- memset(dep, 0, sizeof dep);
- dep[s] = 1;
- q.push(s);
- while (!q.empty()) {
- int x = q.front();
- q.pop();
- for (auto &i: g[x]) {
- Edge &e = edges[i];
- if (!dep[e.to] && e.cap > e.flow) {
- dep[e.to] = dep[x] + 1;
- q.push(e.to);
- }
- }
- }
- return dep[t];
- }
- int dfs (int x, int t, int flow) {
- if (x == t || flow == 0) return flow;
- int res = 0;
- for (int i = cur[x]; i < (int)g[x].size(); i ++) {
- cur[x] = i;
- Edge &e = edges[g[x][i]];
- int y = e.to;
- if (dep[y] == dep[x] + 1) {
- int d = dfs(e.to, t, min(flow - res, e.cap - e.flow));
- res += d;
- edges[g[x][i]].flow += d;
- edges[g[x][i] ^ 1].flow -= d;
- if (res == flow) return res;
- }
- }
- return res;
- }
- int dinic (int s,int t) {
- int maxflow = 0;
- while (bfs(s, t)) {
- memset(cur, 0, sizeof(int) * (n + 1));
- maxflow += dfs(s, t, INF);
- }
- return maxflow;
- }
- void print (int s, int t, int m) {
- queue<int> q;
- vector<bool> vis(n + 1, 0);
- q.push(s);
- vector<int> res;
- while (!q.empty()) {
- int x = q.front();
- q.pop();
- if (vis[x]) continue;
- vis[x] = 1;
- res.push_back(x);
- for (auto &i: g[x]) {
- Edge &e = edges[i];
- if (e.cap > e.flow) q.push(e.to);
- }
- }
- sort(res.begin(), res.end());
- bool f = 0;
- for (auto x: res) {
- if (x == s || x == t) continue;
- if (x > m) {
- if (!f) {
- cout << endl;
- f = 1;
- }
- cout << x - m << ' ';
- }
- else cout << x << ' ';
- }
- cout << endl;
- }
- };
- Dinic dinic;
- vector<int> read () {
- char tools[10000];
- memset(tools,0,sizeof tools);
- cin.getline(tools,10000);
- int ulen=0,tool;
- vector<int> res;
- while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
- {//tool是该实验所需仪器的其中一个
- //这一行,你可以将读进来的编号进行储存、处理,如连边。
- res.push_back(tool);
- if (tool==0)
- ulen++;
- else {
- while (tool) {
- tool/=10;
- ulen++;
- }
- }
- ulen++;
- }
- return res;
- }
- int n, m;
- int p[N];
- void solve() {
- cin >> m >> n;
- int s = 0, t = n + m + 1;
- dinic.init(t);
- int sum = 0;
- for (int i = 1; i <= m; i ++) {
- cin >> p[i];
- sum += p[i];
- dinic.addEdge(s, i, p[i]);
- auto res = read();
- for (auto x: res) {
- dinic.addEdge(i, x + m, INF);
- }
- }
- for (int i = 1; i <= n; i ++) {
- int cost;
- cin >> cost;
- dinic.addEdge(i + m, t, cost);
- }
- int ans = sum - dinic.dinic(s, t);
- dinic.print(s, t, m);
- cout << ans;
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- int _ = 1;
- // cin >> _;
- while (_--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement