Author : Dipu Kumar Mohanto
CSE, Batch - 6
BRUR.
Problem Statement : B. Just change it up so it doesn't look like you copied...
Source : Codemarshal
Kuet IUPC'19
Category : Graph Theory
Algorithm : Min Cost Max Flow, Lexicographical Min Cost Max Flow
Verdict : Accepted
- #include "bits/stdc++.h"
-
- using namespace std;
-
- static const int maxn = 15 + 5;
- static const int Max = 1000 + 5;
-
- string paragraph[maxn];
- vector <string> sentence[maxn];
- vector <string> allSentences;
- vector <int> priority[maxn];
- vector <int> which[Max];
- map <string, int> mapper;
- map <int, string> rmapper;
-
- struct Edge
- {
- int to;
- int flow;
- int cap;
- int cost;
- int rev;
- Edge(int to = 0, int flow = 0, int cap = 0, int cost = 0, int rev = 0)
- : to(to)
- , flow(flow)
- , cap(cap)
- , cost(cost)
- , rev(rev) {}
- };
-
- struct MinCostMaxFlow
- {
- int nodes;
- vector <int> prio;
- vector <int> curflow;
- vector <int> prevEdge;
- vector <int> prevnode;
- vector <int> q;
- vector <int> pot;
- vector <bool> inqueue;
- vector< vector<Edge> > graph;
-
- MinCostMaxFlow() {}
- MinCostMaxFlow(int n)
- : nodes(n)
- , prio(n, 0)
- , curflow(n, 0)
- , prevEdge(n, 0)
- , prevnode(n, 0)
- , q(n, 0)
- , pot(n, 0)
- , inqueue(n, 0)
- , graph(n) {}
-
- void addEdge(int source, int to, int capacity, int cost)
- {
- Edge a = {to, 0, capacity, cost, (int)graph[to].size()};
- Edge b = {source, 0, 0, -cost, (int)graph[source].size()};
- graph[source].push_back(a);
- graph[to].push_back(b);
- }
- void bellman_ford(int source, vector<int> &dist)
- {
- fill(dist.begin(), dist.end(), INT_MAX);
- dist[source] = 0;
- int qt=0;
- q[qt++] = source;
- for(int qh = 0;(qh-qt) % nodes != 0; qh++)
- {
- int u = q[qh % nodes];
- inqueue[u] = false;
- for(auto &e : graph[u])
- {
- if(e.flow >= e.cap) continue;
- int v = e.to;
- int newDist = dist[u] + e.cost;
- if(dist[v] > newDist)
- {
- dist[v] = newDist;
- if(!inqueue[v])
- {
- inqueue[v] = true;
- q[qt++ % nodes] = v;
- }
- }
- }
- }
- }
- pair<int, int> minCostFlow(int source, int dest, int maxflow)
- {
- bellman_ford(source, pot);
- int flow = 0;
- int flow_cost = 0;
- while(flow < maxflow)
- {
- priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;
- q.push({0, source});
- fill(prio.begin(), prio.end(), INT_MAX);
- prio[source] = 0;
- curflow[source] = INT_MAX;
- while(!q.empty())
- {
- int d = q.top().first;
- int u = q.top().second;
- q.pop();
- if(d != prio[u]) continue;
- for(int i = 0; i < graph[u].size(); i++)
- {
- Edge &e=graph[u][i];
- int v = e.to;
- if(e.flow >= e.cap) continue;
- int newPrio = prio[u] + e.cost + pot[u] - pot[v];
- if(prio[v] > newPrio)
- {
- prio[v] = newPrio;
- q.push({newPrio, v});
- prevnode[v] = u;
- prevEdge[v] = i;
- curflow[v] = min(curflow[u], e.cap - e.flow);
- }
- }
- }
- if(prio[dest] == INT_MAX) break;
- for(int i = 0;i < nodes; i++) pot[i] += prio[i];
- int df = min(curflow[dest], maxflow - flow);
- flow += df;
- for(int v = dest; v!= source; v = prevnode[v])
- {
- Edge &e = graph[ prevnode[v] ][ prevEdge[v] ];
- e.flow += df;
- graph[v][e.rev].flow -= df;
- flow_cost += df * e.cost;
- }
- }
- return {flow, flow_cost};
- }
- int flow(int u)
- {
- int maxi = 0;
- for (Edge g : graph[u]) maxi = max(maxi, g.flow);
- return maxi;
- }
- };
-
- void clean()
- {
- mapper.clear();
- rmapper.clear();
- allSentences.clear();
- for (int i = 0; i < maxn; i++)
- {
- priority[i].clear();
- sentence[i].clear();
- }
- for (int i = 0; i < 1000 + 5; i++)
- {
- which[i].clear();
- }
- }
-
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
-
-
-
-
-
- int tc;
- cin >> tc;
- for (int tcase = 1; tcase <= tc; tcase++)
- {
- clean();
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++)
- {
- cin >> paragraph[i];
- string s;
- for (char ch : paragraph[i])
- {
- if (ch == '.')
- {
- assert(s.empty() == false);
- sentence[i].push_back(s);
- allSentences.push_back(s);
- s.clear();
- }
- else
- {
- s.push_back(ch);
- }
- }
- if (s.empty() == false)
- {
- sentence[i].push_back(s);
- allSentences.push_back(s);
- s.clear();
- }
- }
- int k;
- cin >> k;
- sort(allSentences.begin(), allSentences.end());
- int ptr = 0;
- for (string str : allSentences)
- {
- if (mapper.find(str) == mapper.end())
- {
- mapper[str] = ++ptr;
- rmapper[ptr] = str;
- }
- }
- for (int i = 1; i <= n; i++)
- {
- for (int j = 0; j < sentence[i].size(); j++)
- {
- priority[i].push_back(mapper[ sentence[i][j] ]);
- }
- sort(priority[i].begin(), priority[i].end());
- for (int x : priority[i]) which[x].push_back(i);
- }
- int nodes = 3 + n + ptr;
- MinCostMaxFlow mcmf(nodes);
- int source = 0;
- int sink = nodes - 2;
- int superSink = nodes - 1;
- for (int i = 1; i <= n; i++)
- {
- mcmf.addEdge(source, i, 1, 0);
- for (int j = 0; j < priority[i].size(); j++)
- {
- mcmf.addEdge(i, n + priority[i][j], 1, priority[i][j]);
- }
- }
- for (int i = 1; i <= ptr; i++)
- {
- mcmf.addEdge(n + i, sink, 1, 0);
- }
- mcmf.addEdge(sink, superSink, 1000, 0);
- pair <int, int> maxFlow = mcmf.minCostFlow(source, superSink, 1000);
- vector <int> sol;
- for (int i = 1; i <= ptr; i++)
- {
- int flow = mcmf.flow(n + i);
- if (flow == 1) sol.push_back(i);
- }
- vector <bool> vis(n + 1, 0);
- vector <int> res;
- for (int x : sol)
- {
- if (res.size() == k) break;
- bool ok = false;
- for (int y : which[x])
- {
- if (vis[y]) ok = true;
- }
- if (ok) continue;
- res.push_back(x);
- for (int y : which[x]) vis[y] = 1;
- }
- cout << "Case " << tcase << ": ";
- if (res.size() < k)
- {
- cout << "impossible\n";
- }
- else
- {
- for (int i = 0; i < k; i++)
- {
- cout << rmapper[ res[i] ];
- if (i == k - 1) cout << '\n';
- else cout << ".";
- }
- }
- }
- }
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.