首页 > ACM题库 > HDU-杭电 > HDU 3505-Writing Robot-字典树-[解题报告]HOJ
2014
04-09

HDU 3505-Writing Robot-字典树-[解题报告]HOJ

Writing Robot

问题描述 :

Word’s combination is an interesting thing.
Given a set of words S={s1, s2, …, sn}, where si is a word only consists lowercase letter and its length is less than 50. When si merges in a text, its effect on reader’s mood is both positive and negative. A word’s positive effect is measured in love level li and negative effect is in hate level hi.
At the same time, given a set paragraph P={P1, P2, …, Pn} and Pj is a string whose length is less than 1000. For each word si in S, there is two conditions in Pj as follows:
Related : si is a substring of Pj, and li units of love level is added to Pj, if si occurs several times in Pj, every occurrence is counted.
Unrelated : si never occurs in Pj and this condition bring Pj nothing.
Text T is defined as a subset of P. T’s love level is defined as sum of Pj’s love level where Pj belongs to T minus words?hate level. Because a strange psychology phenomenon, hate level of a word which occurs in T is only counted once no matter how many times it occurs.
Given the set of S and P, writing robot’s job is to select a subset T to maximum the love level.

输入:

The first line of the input contains a single integer T (1 ≤ T ≤ 15), the number of test cases. Then T cases follow.
First line of each case contains 2 integers, S, P. (1≤S, P≤150), then S lines follows, each line contains 2 integers, li, hi, (1≤li≤100, 1≤hi≤1000), and a string si with length less than 50. Next P lines, each contains a string Pi with length less than 1000. It guarantees that the answer will not exceed 32-bit signed integer.

输出:

The first line of the input contains a single integer T (1 ≤ T ≤ 15), the number of test cases. Then T cases follow.
First line of each case contains 2 integers, S, P. (1≤S, P≤150), then S lines follows, each line contains 2 integers, li, hi, (1≤li≤100, 1≤hi≤1000), and a string si with length less than 50. Next P lines, each contains a string Pi with length less than 1000. It guarantees that the answer will not exceed 32-bit signed integer.

样例输入:

2
3 2
2 2 hit
1 2 it
3 1 song
hitman
singasong
2 2
2 3 ab
1 6 ba
ababab
bababa

样例输出:

Case 1: 2
Case 2: 6

Hint
In the first case, T maybe {""}, {"hitman"}, {"singasong"},{"hitman", "singasong"} and their love level is 0, -1, 2, 1. So "singasong" is chosen. In the second case, cause "ab" and "ba" all occurs in P1 and P2, obviously choosing them both as T={"ababab", "bababa"} will get most love level.


悲剧题,最后时候都没有出,原来是自己字典树忘记清零了,囧~ 其他的就是网络流水题了,模型很好想,也就不多说什么了。

 

C++语言: hdu 3505
001 #include <cstdio>
002 #include <cstring>
003 #include <algorithm>
004 using namespace std;
005 #define MAXN 160
006
007 const int N = MAXN * 2 + 2, E = MAXN * 2 + MAXN * MAXN;
008 /*==================================================*\
009 | Dinic最大流 O(V^2 * E)
010 | INIT: g.build(n); g.add_edge()加入所有弧;
011 | CALL: g.max_flow(s, t); 答案保存在 g._cost 中
012 \*==================================================*/
013 typedef long long typec; // type of cost
014 const typec inf = 0x3f3f3f3f3f3f3f3fLL; // max of cost
015
016 struct NetWork {
017     int _n, _ne, _head[N], _cur[N], _ps[N], _dep[N];
018     typec _cost;
019
020     struct Edge {
021         int _x, _y, _next;
022         typec _c;
023     } _bf[E * 2 + 2];
024
025     void add_edge(int x, int y, typec c) { // add an arc(x -> y, c); vertex: 0 ~ n-1;
026         _bf[_ne]._x = x; _bf[_ne]._y = y; _bf[_ne]._c = c;
027         _bf[_ne]._next = _head[x]; _head[x] = _ne++;
028         _bf[_ne]._x = y; _bf[_ne]._y = x; _bf[_ne]._c = 0;
029         _bf[_ne]._next = _head[y]; _head[y] = _ne++;
030     }
031
032     inline void build(int n) {
033         _n = n; _ne = 2;
034         memset(_head, 0, n * sizeof (int));
035     }
036
037     typec max_flow(int s, int t) {
038         typec tr, res = 0;
039         int i, j, k, f, r, top;
040         while (1) {
041             memset(_dep, -1, _n * sizeof (int));
042             for (f = _dep[_ps[0] = s] = 0, r = 1; f != r;)
043                 for (i = _ps[f++], j = _head[i]; j; j = _bf[j]._next) {
044                     if (_bf[j]._c && -1 == _dep[k = _bf[j]._y]) {
045                         _dep[k] = _dep[i] + 1;
046                         _ps[r++] = k;
047                         if (k == t) {
048                             f = r;
049                             break;
050                         }
051                     }
052                 }
053             if (-1 == _dep[t]) break;
054             memcpy(_cur, _head, _n * sizeof (int));
055             for (i = s, top = 0;;) {
056                 if (i == t) {
057                     for (k = 0, tr = inf; k < top; ++k)
058                         if (_bf[_ps[k]]._c < tr)
059                             tr = _bf[_ps[f = k]]._c;
060                     for (k = 0; k < top; ++k)
061                         _bf[_ps[k]]._c -= tr, _bf[_ps[k]^1]._c += tr;
062                     res += tr;
063                     i = _bf[_ps[top = f]]._x;
064                 }
065                 for (j = _cur[i]; _cur[i]; j = _cur[i] = _bf[_cur[i]]._next)
066                     if (_bf[j]._c && _dep[i] + 1 == _dep[_bf[j]._y]) break;
067                 if (_cur[i]) {
068                     _ps[top++] = _cur[i];
069                     i = _bf[_cur[i]]._y;
070                 } else {
071                     if (0 == top) break;
072                     _dep[i] = -1;
073                     i = _bf[_ps[--top]]._x;
074                 }
075             }
076         }
077         return _cost = res;
078     }
079 } g;
080
081 int n, m;
082 long long love[MAXN], hate[MAXN];
083
084 //////////////////////////////////////////////
085 struct Trie {
086     Trie* next[26];
087     int terminate;
088 } nodes[MAXN * 600], *ptr;
089
090 void insert_trie(char* s, int no) {
091     Trie* root = nodes;
092     for (int i = 0; s[i]; ++i) {
093         if (root->next[s[i] - ‘a’] == 0) {
094             root->next[s[i] - ‘a’] = ++ptr;
095             memset(ptr, 0, sizeof(Trie));    // notice!!!!
096             ptr->terminate = -1;
097         }
098         root = root->next[s[i] - ‘a’];
099     }
100     if (root->terminate != -1) {
101         love[no] += love[root->terminate];
102         hate[no] += hate[root->terminate];
103     }
104     root->terminate = no;
105 }
106
107 long long slove[MAXN];
108 bool map[MAXN][MAXN];
109
110 void find_trie(char* s, int noo) {
111     Trie* root = nodes;
112     for (int i = 0; s[i]; ++i)
113         if (root->next[s[i] - ‘a’]) {
114             root = root->next[s[i] - ‘a’];
115             if (root->terminate != -1) {
116                 slove[noo] += love[root->terminate];
117                 map[noo][root->terminate] = true;
118             }
119         } else
120             return;
121 }
122 ///////////////////////////////////////////////
123
124 inline int pointS(int x) {
125     return x;
126 }
127
128 inline int pointP(int x) {
129     return n + x;
130 }
131
132 char buf[20000];
133
134 int main() {
135 #ifndef ONLINE_JUDGE
136     freopen(“in.txt”, “r”, stdin);
137     freopen(“out.txt”, “w”, stdout);
138 #endif
139     int test;
140     scanf(“%d”, &test);
141     for (int cas = 1; cas <= test; ++cas) {
142         memset(slove, 0, sizeof(slove));
143         memset(map, 0, sizeof(map));
144         ptr = nodes;
145         memset(ptr, 0, sizeof(Trie));        // notice!!!!
146
147         scanf(“%d%d”, &n, &m);
148         for (int i = 0; i < n; ++i) {
149             scanf(“%I64d%I64d%s”, love + i, hate + i, buf);
150             insert_trie(buf, i);
151         }
152         for (int i = 0; i < m; ++i) {
153             scanf(“%s”, buf);
154             int len = strlen(buf);
155             for (int j = 0; j < len; ++j)
156                 find_trie(buf + j, i);
157         }
158         g.build(n + m + 2);
159         int src = n + m, sink = n + m + 1;
160         for (int i = 0; i < n; ++i)
161             g.add_edge(pointS(i), sink, hate[i]);
162         long long sum = 0;
163         for (int i = 0; i < m; ++i) {
164             g.add_edge(src, pointP(i), slove[i]);
165             sum += slove[i];
166         }
167         for (int i = 0; i < n; ++i)
168             for (int j = 0; j < m; ++j)
169                 if (map[j][i])
170                     g.add_edge(pointP(j), pointS(i), inf);
171         printf(“Case %d: %I64d\n, cas, sum - g.max_flow(src, sink));
172     }
173     return 0;
174 }
参考:http://xpycc.blog.163.com/blog/static/50266902201072491946947/


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?