SRM 404 DIV1 Hard SoftwareCompanies
問題
いくつかの企業がある。それぞれの企業はデータを処理して独自形式のデータにする。
企業はそれぞれデータの処理数に上限がある。また、処理できるデータの形式にも制限がある。もちろん、データ処理の仕事の依頼にはコストがかかる。これは、処理するデータ量にかからわず、1データでも処理するなら定額のコストとなる。
i番目の企業の企業名を表すnames[i]、処理できるデータ形式の集合を表すprocess[i]、仕事依頼のコストを表すcost[i]、処理数の制限を表すamount[i]がそれぞれ与えられる。
さらに企業名company1とcompany2が与えられる。company1の形式のデータをcompany2の形式のデータに処理したい。処理できるデータ量はできるだけ多くしたい。その中でかかる合計のコストを少なくしたい。そのうちで辞書順最小の企業名のリストをvector
- 2 ≦ |names| ≦ 12
- 0 ≦ cost[i] ≦ 1000000
- 1 ≦ amount[i] ≦ 1000000
- company1 ≠ company2
解答
依頼する企業の集合を全探索する。
それぞれに対して普通に最大流をする。頂点に容量制限があるが、これは頂点を2倍にするテクニックでやればよい。
コード
#include <string> #include <vector> #include <algorithm> #include <sstream> #include <cstring> #include <queue> #include <map> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define INF 0x3f3f3f3f using namespace std; typedef pair<int,int> pii; typedef vector<string> vs; typedef int Weight; struct Edge { int src, dst; Weight cost; Edge(int s, int d, Weight w) : src(s), dst(d), cost(w) { } }; bool operator < (const Edge &e, const Edge &f) { return e.cost != f.cost ? e.cost > f.cost : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; #define RESIDUE(s,t) (capacity[s][t]-flow[s][t]) Weight augment(const Graph &g, const Matrix &capacity, Matrix &flow, const vector<int> &level, vector<bool> &finished, int u, int t, Weight cur) { if (u == t || cur == 0) return cur; if (finished[u]) return 0; finished[u] = true; each(e, g[u]) if (level[e->dst] > level[u]) { Weight f = augment(g, capacity, flow, level, finished, e->dst, t, min(cur, RESIDUE(u, e->dst))); if (f > 0) { flow[u][e->dst] += f; flow[e->dst][u] -= f; finished[u] = false; return f; } } return 0; } Weight maximumFlow(const Graph &g, int s, int t) { int n = g.size(); Matrix flow(n, Array(n)), capacity(n, Array(n)); // adj. matrix rep(u,n) each(e,g[u]) capacity[e->src][e->dst] += e->cost; Weight total = 0; for (bool cont = true; cont; ) { cont = false; vector<int> level(n, -1); level[s] = 0; // make layered network queue<int> Q; Q.push(s); for (int d = n; !Q.empty() && level[Q.front()] < d; ) { int u = Q.front(); Q.pop(); if (u == t) d = level[u]; each(e, g[u]) if (RESIDUE(u,e->dst) > 0 && level[e->dst] == -1) Q.push(e->dst), level[e->dst] = level[u] + 1; } vector<bool> finished(n); // make blocking flows for (Weight f = 1; f > 0; ) { f = augment(g, capacity, flow, level, finished, s, t, INF); if (f == 0) break; total += f; cont = true; } } return total; } void createRev(const Graph& g, Graph &r) { r.assign(g.size(), Edges()); each(i, g) each(j, *i) { r[j->src].pb(*j); r[j->dst].pb(Edge(j->dst, j->src, 0)); } } struct SoftwareCompanies { pii solve(int mask, vector <string> names, vector <string> process, vector <int> cost, vector <int> amount, string company1, string company2) { int n = names.size(); Graph g(n*2+2); int s = n*2, t = s+1; map<string,int> a; rep(i, n) a[names[i]] = i; rep(i, n) if(mask >> i & 1) g[n+i].pb(Edge(n+i, i, amount[i])); rep(i, n) { stringstream ss(process[i]); string q; while(ss >> q) { int j = a[q]; g[i].pb(Edge(i, n + j, INF)); } } int c1 = a[company1], c2 = a[company2]; g[s].pb(Edge(s, n + c1, INF)); g[c2].pb(Edge(c2, t, INF)); int c = 0; rep(i, n) if(mask >> i & 1) c += cost[i]; Graph gg; createRev(g, gg); return mp(-maximumFlow(gg, s, t), c); } vector <string> produceData(vector <string> names, vector <string> process, vector <int> cost, vector <int> amount, string company1, string company2) { int n = names.size(); pair<pii,vs> r(pii(INF,0),vs()); rep(i, 1<<n) { vs v; rep(j, n) if(i >> j & 1) v.pb(names[j]); sort(all(v)); r = min(r, mp(solve(i, names, process, cost, amount, company1, company2), v)); } return r.second; } };
