AOJ 2457 - Adhoc Translation
問題文 : Adhoc Translation
解法 :
これがA 問題ってやべえなあ...
辞書に登録されている単語とネットで見た単語の間に, それぞれ編集距離をコストとした辺を張る.
ネットで見た単語の数 ≦ 辞書に登録されている単語の数で, かならずネットで見た単語の数の分だけマッチングが出来る.
コストが最小になるようにすればいいので, 辺の容量を1 とし, ネットで見た単語の数を流量とした最小費用流を流せば良い.
コード :
#include <cstdio> #include <cstring> #include <string> #include <queue> #include <map> #include <algorithm> #include <vector> using namespace std; typedef pair<int, int> P; struct edge { int to, cap, cost, rev; }; int V; vector<edge> G[50200]; int h[50200], dist[50200]; int prevv[50200], preve[50200]; void addEdge(int from, int to, int cap, int cost) { G[from].push_back((edge){to, cap, cost, G[to].size()}); G[to].push_back((edge){from, 0, -cost, G[from].size() - 1}); } int minCostFlow(int s, int t, int f) { int res = 0; fill(h, h + V, 0); while (f > 0){ priority_queue<P, vector<P>, greater<P> > pq; fill(dist, dist + V, 1000000000); dist[s] = 0; pq.push(P(0, s)); while (!pq.empty()){ P p = pq.top(); pq.pop(); int v = p.second; if (dist[v] < p.first) continue; for (int i = 0; i < G[v].size(); i++){ edge &e = G[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){ dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; pq.push(P(dist[e.to], e.to)); } } } if (dist[t] == 1000000000) return (-1); for (int v = 0; v < V; v++) h[v] += dist[v]; int d = f; for (int v = t; v != s; v = prevv[v]){ d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += d * h[t]; for (int v = t; v != s; v = prevv[v]){ edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return (res); } int getDist(string s, string t) { int dp[32][32]; for (int i = 0; i <= s.size(); i++) dp[i][0] = i; for (int i = 0; i <= t.size(); i++) dp[0][i] = i; for (int i = 1; i <= s.size(); i++) for (int j = 1; j <= t.size(); j++) dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + (s[i - 1] != t[j - 1])); return (dp[s.size()][t.size()]); } int main() { int N, M; vector<string> S, T; map<string, int> c; scanf("%d %d", &N, &M); getchar(); for (int i = 0; i < N; i++){ char st[1024], *p; fgets(st, sizeof(st), stdin); p = strtok(st, " \n"); while (p != NULL){ S.push_back((string)p); if (c.count((string)p) == 0) c[(string)p] = 0; c[(string)p]++; p = strtok(NULL, " \n"); } } sort(S.begin(), S.end()); S.erase(unique(S.begin(), S.end()), S.end()); for (int i = 0; i < M; i++){ char st[1024]; scanf("%s", st); T.push_back((string)st); } sort(T.begin(), T.end()); T.erase(unique(T.begin(), T.end()), T.end()); V = S.size() + T.size() + 2; for (int i = 0; i < S.size(); i++){ addEdge(0, i + 1, 1, 0); for (int j = 0; j < T.size(); j++){ addEdge(i + 1 , S.size() + j + 1, 1, c[S[i]] * getDist(S[i], T[j])); if (!i) addEdge(S.size() + j + 1, S.size() + T.size() + 1, 1, 0); } } printf("%d\n", minCostFlow(0, S.size() + T.size() + 1, S.size())); return (0); }