PS와 개발을 공부하자

UVa OJ 11381 - Elegant Strings 본문

Algorithm/Problem Solving

UVa OJ 11381 - Elegant Strings

sgc109 2017.07.07 01:55
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2376




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
struct edge{
    int to,cap,cost,rev;
};
vector<edge> G[203];
map<int,int> mp;
int dist[203];
int par[203];
int edgeIdx[203];
int inQ[203];
int trans(string s){
    int ret = 0;
    for(int i = 0 ; i < (int)s.size(); i++){
        ret = ret * 26 + s[i]-'a';
    }
    return ret;
}
int HEAD(int x){
    return 2 + x;
}
int TAIL(int x){
    return 2 + 100 + x;
}
void connect(int from, int to, int cap, int cost){
    G[from].push_back({to, cap, cost, (int)G[to].size()});
    G[to].push_back({from, 0-cost, (int)G[from].size()-1});
}
pair<int,int> mcmf(int src, int sink){
    int maxFlow = 0, minCost = 0;
    while(1){
        memset(inQ,0,sizeof(inQ));
        memset(dist,0x3c,sizeof(dist));
        queue<int> q;
        q.push(src);
        dist[src] = 0;
        while(!q.empty()){
            int here = q.front();
            q.pop();
            inQ[here] = 0;
            for(int i = 0 ; i < (int)G[here].size(); i++){
                auto& e = G[here][i];
                if(e.cap <= 0continue;
                if(dist[e.to] > dist[here] + e.cost) {
                    par[e.to] = here;
                    edgeIdx[e.to] = i;
                    dist[e.to] = dist[here] + e.cost;
                    if(!inQ[e.to]) inQ[e.to] = 1, q.push(e.to);
                }
            }
        }
        if(dist[sink] == inf) break;
        int minFlow = inf;
        int costSum = 0;
        for(int p = sink; p != src; p = par[p]){
            auto e = G[par[p]][edgeIdx[p]];
            minFlow = min(minFlow, e.cap);
            costSum += e.cost;
        }
        for(int p = sink; p != src; p = par[p]){
            auto& e = G[par[p]][edgeIdx[p]];
            e.cap -= minFlow;
            G[e.to][e.rev].cap += minFlow;
        }
        maxFlow += minFlow;
        minCost += costSum * minFlow;
    }
    return {maxFlow, minCost};
}
int main() {
    int src = 0, sink = 1;
    int X;
    cin >> X;
    while(X--){
        mp.clear();
        for(int i = 0 ; i < 203; i++) G[i].clear();
        string s1, s2;
        cin >> s1 >> s2;
        for(int i = 0 ; i < (int)s1.size() -1; i++){
            string stmp = s1.substr(i, 2);
            int h = trans(stmp);
            if(mp[h] == 0) mp[h] = (i+1)*(i+1);
        }
        for(int i = 0 ; i < (int)s2.size(); i++){
            for(int j = i+1; j < (int)s2.size(); j++){
                string stmp;
                stmp += s2[i];
                stmp += s2[j];
                int h = trans(stmp);
                if(mp[h] != 0) connect(TAIL(i), HEAD(j), 1, mp[h]);
            }
        }
        for(int i = 0; i < (int)s2.size(); i++) connect(src, TAIL(i), 10);
        for(int i = 0; i < (int)s2.size(); i++) connect(HEAD(i), sink, 10);
        pair<int,int> ret = mcmf(src, sink);
        cout << (int)s2.size() - ret.first << " " << ret.second << endl;
    }
    return 0;
}
cs


'Algorithm > Problem Solving' 카테고리의 다른 글

Topcoder SRM 527 Div1(Easy) P8XGraphBuilder  (0) 2017.07.14
BOJ 1444번 숌 언어  (0) 2017.07.09
UVa OJ 11381 - Elegant Strings  (0) 2017.07.07
CSacademy) Tree Nodes Sets  (0) 2017.07.06
BOJ 1804번 랩싸기  (0) 2017.07.06
BOJ 11570번 환상의 듀엣  (0) 2017.07.05
0 Comments
댓글쓰기 폼