Advertisement
wym1111

Untitled

Aug 2nd, 2024
239
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.38 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. #define endl '\n'
  6. const int N = 1e2 + 10;
  7. const int INF = 0x3f3f3f3f;
  8.  
  9. class Dinic {
  10. private:
  11.     struct Edge {
  12.         int from, to, cap, flow;
  13.         Edge (int u, int v, int c, int f) :
  14.         from(u), to(v), cap(c), flow(f){}
  15.     };
  16.     vector<Edge> edges;
  17.     vector<int> g[N];
  18.     int dep[N], cur[N];
  19.     int n;
  20. public:
  21.     void init (int _n) {
  22.         n = _n;
  23.         for (int i = 0; i <= n; i ++) {
  24.             g[i].clear();
  25.         }
  26.         edges.clear();
  27.     }
  28.     void addEdge (int u, int v, int c) {
  29.         edges.push_back({u, v, c, 0});
  30.         edges.push_back({v, u, 0, 0});
  31.         int m = edges.size();
  32.         g[u].push_back(m - 2);
  33.         g[v].push_back(m - 1);
  34.     }
  35.     int bfs (int s, int t) {
  36.         queue<int> q;
  37.         memset(dep, 0, sizeof dep);
  38.         dep[s] = 1;
  39.         q.push(s);
  40.         while (!q.empty()) {
  41.             int x = q.front();
  42.             q.pop();
  43.             for (auto &i: g[x]) {
  44.                 Edge &e = edges[i];
  45.                 if (!dep[e.to] && e.cap > e.flow) {
  46.                     dep[e.to] = dep[x] + 1;
  47.                     q.push(e.to);
  48.                 }
  49.             }
  50.         }
  51.         return dep[t];
  52.     }
  53.     int dfs (int x, int t, int flow) {
  54.         if (x == t || flow == 0) return flow;
  55.         int res = 0;
  56.         for (int i = cur[x]; i < (int)g[x].size(); i ++) {
  57.             cur[x] = i;
  58.             Edge &e = edges[g[x][i]];
  59.             int y = e.to;
  60.             if (dep[y] == dep[x] + 1) {
  61.                 int d = dfs(e.to, t, min(flow - res, e.cap - e.flow));
  62.                 res += d;
  63.                 edges[g[x][i]].flow += d;
  64.                 edges[g[x][i] ^ 1].flow -= d;
  65.                 if (res == flow) return res;
  66.             }
  67.         }
  68.         return res;
  69.     }
  70.     int dinic (int s,int t) {
  71.         int maxflow = 0;
  72.         while (bfs(s, t)) {
  73.             memset(cur, 0, sizeof(int) * (n + 1));
  74.             maxflow += dfs(s, t, INF);
  75.         }
  76.         return maxflow;
  77.     }
  78.     void print (int s, int t, int m) {
  79.         queue<int> q;
  80.         vector<bool> vis(n + 1, 0);
  81.         q.push(s);
  82.         vector<int> res;
  83.         while (!q.empty()) {
  84.             int x = q.front();
  85.             q.pop();
  86.             if (vis[x]) continue;
  87.             vis[x] = 1;
  88.             res.push_back(x);
  89.             for (auto &i: g[x]) {
  90.                 Edge &e = edges[i];
  91.                 if (e.cap > e.flow) q.push(e.to);
  92.             }
  93.         }
  94.         sort(res.begin(), res.end());
  95.         bool f = 0;
  96.         for (auto x: res) {
  97.             if (x == s || x == t) continue;
  98.             if (x > m) {
  99.                 if (!f) {
  100.                     cout << endl;
  101.                     f = 1;
  102.                 }
  103.                 cout << x - m << ' ';
  104.             }
  105.             else cout << x << ' ';
  106.         }
  107.         cout << endl;
  108.     }
  109. };
  110. Dinic dinic;
  111.  
  112. vector<int> read () {
  113.     char tools[10000];
  114.     memset(tools,0,sizeof tools);
  115.     cin.getline(tools,10000);
  116.     int ulen=0,tool;
  117.     vector<int> res;
  118.     while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
  119.     {//tool是该实验所需仪器的其中一个      
  120.         //这一行,你可以将读进来的编号进行储存、处理,如连边。
  121.         res.push_back(tool);
  122.         if (tool==0)
  123.             ulen++;
  124.         else {
  125.             while (tool) {
  126.                 tool/=10;
  127.                 ulen++;
  128.             }
  129.         }
  130.         ulen++;
  131.     }
  132.     return res;
  133. }
  134.  
  135. int n, m;
  136. int p[N];
  137.  
  138. void solve() {
  139.     cin >> m >> n;
  140.     int s = 0, t = n + m + 1;
  141.     dinic.init(t);
  142.     int sum = 0;
  143.     for (int i = 1; i <= m; i ++) {
  144.         cin >> p[i];
  145.         sum += p[i];
  146.         dinic.addEdge(s, i, p[i]);
  147.         auto res = read();
  148.         for (auto x: res) {
  149.             dinic.addEdge(i, x + m, INF);
  150.         }
  151.     }
  152.     for (int i = 1; i <= n; i ++) {
  153.         int cost;
  154.         cin >> cost;
  155.         dinic.addEdge(i + m, t, cost);
  156.     }
  157.     int ans = sum - dinic.dinic(s, t);
  158.     dinic.print(s, t, m);
  159.     cout << ans;
  160. }
  161.  
  162. signed main() {
  163.     ios::sync_with_stdio(false);
  164.     cin.tie(0), cout.tie(0);
  165.     int _ = 1;
  166. //  cin >> _;
  167.     while (_--){
  168.         solve();
  169.     }
  170.     return 0;
  171. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement