挺好的一道題目，我的做法是kmp+Dinic網(wǎng)絡流。
kmp求子串在P中出現(xiàn)的次數(shù)，從而計算love值。
網(wǎng)絡流主要用來處理最優(yōu)解。
case2中p1的love值是8，p2的love值是7，最終T包含p1和p2，hate值也僅僅算一次。
這個題目難點在于思考為什么網(wǎng)絡流的解法是合理，可以反證。從而導出最優(yōu)解等于love的總和-最大流。
建圖方法：
source連接p，初始容量為love值；
p連接s，初始容量為INF;
s連接destination，容量為hate值。
在最優(yōu)解中，如果s到des的流量小于容量，則證明包含s的p都不被選擇。即減去p的容量和。如果流量大于等于容量，則證明該直接去掉hate值。

1 /* 3505 */ 2 #include <iostream> 3 #include <string> 4 #include <map> 5 #include <queue> 6 #include <set> 7 #include <stack> 8 #include <vector> 9 #include <deque> 10 #include <algorithm> 11 #include <cstdio> 12 #include <cmath> 13 #include <ctime> 14 #include <cstring> 15 #include <climits> 16 #include <cctype> 17 #include <cassert> 18 #include <functional> 19 #include <iterator> 20 #include <iomanip> 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set<int> 25 #define stpii set<pair<int, int> > 26 #define mpii map<int,int> 27 #define vi vector<int> 28 #define pii pair<int,int> 29 #define vpii vector<pair<int,int> > 30 #define rep(i, a, n) for (int i=a;i<n;++i) 31 #define per(i, a, n) for (int i=n-1;i>=a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 typedef struct { 43 int l, h, len; 44 char s[54]; 45 int nxt[54]; 46 47 void getnext() { 48 int i = 0, j = -1; 49 50 nxt[0] = -1; 51 while (i < len) { 52 if (j==-1 || s[i]==s[j]) { 53 ++i; 54 ++j; 55 nxt[i] = j; 56 } else { 57 j = nxt[j]; 58 } 59 } 60 } 61 62 int kmp(char *d) { 63 int dlen = strlen(d); 64 int i = 0, j =0; 65 int ret = 0; 66 67 while (i < dlen) { 68 if (d[i] == s[j]) { 69 ++i; 70 ++j; 71 } else { 72 j = nxt[j]; 73 if (j == -1) { 74 j = 0; 75 ++i; 76 } 77 } 78 if (j == len) { 79 ++ret; 80 j = nxt[j]; 81 } 82 } 83 84 return ret; 85 } 86 87 } node_t; 88 89 typedef struct { 90 int v, f, nxt; 91 } edge_t; 92 93 const int INF = 0x3f3f3f3f; 94 const int maxn = 155; 95 const int maxv = maxn * 2; 96 const int maxl = 1005; 97 const int maxe = 1e5+5; 98 node_t nd[maxn]; 99 bool M[maxn][maxn]; 100 int score[maxn]; 101 int head[maxv], head_[maxv]; 102 edge_t E[maxe]; 103 int dis[maxv]; 104 int Q[maxv]; 105 char s[maxl]; 106 int nxt[maxl]; 107 int sn, pn, m; 108 109 int calc(int k) { 110 int ret = 0, cnt; 111 112 rep(i, 1, sn+1) { 113 cnt = nd[i].kmp(s); 114 if (cnt) { 115 ret += nd[i].l * cnt; 116 M[k][i] = true; 117 } 118 } 119 120 return ret; 121 } 122 123 void init() { 124 m = 0; 125 memset(head, -1, sizeof(head)); 126 memset(M, false, sizeof(M)); 127 } 128 129 void addEdge(int u, int v, int f) { 130 E[m].v = v; 131 E[m].f = f; 132 E[m].nxt = head[u]; 133 head[u] = m++; 134 135 E[m].v = u; 136 E[m].f = 0; 137 E[m].nxt = head[v]; 138 head[v] = m++; 139 } 140 141 bool bfs(int s, int t) { 142 int l = 0, r = 0; 143 int u, v, k; 144 145 Q[r++] = s; 146 memset(dis, 0, sizeof(dis)); 147 dis[s] = 1; 148 149 while (l < r) { 150 u = Q[l++]; 151 for (k=head[u]; k!=-1; k=E[k].nxt) { 152 v = E[k].v; 153 if (!dis[v] && E[k].f) { 154 dis[v] = dis[u] + 1; 155 if (v == t) 156 return false; 157 Q[r++] = v; 158 } 159 } 160 } 161 162 return true; 163 } 164 165 int dfs(int u, int t, int val) { 166 if (u==t || val==0) 167 return val; 168 169 int ret = 0; 170 int v, tmp; 171 172 for (int& k=head_[u]; k!=-1; k=E[k].nxt) { 173 v = E[k].v; 174 if (E[k].f && dis[v]==dis[u]+1 && (tmp=dfs(v, t, min(val, E[k].f)))>0) { 175 E[k].f -= tmp; 176 E[k^1].f += tmp; 177 ret += tmp; 178 val -= tmp; 179 if (val == 0) 180 return ret; 181 } 182 } 183 184 return ret; 185 } 186 187 int Dinic(int s, int t) { 188 int ret = 0, tmp; 189 190 while (1) { 191 if (bfs(s, t)) 192 break; 193 194 memcpy(head_, head, sizeof(head)); 195 while (1) { 196 tmp = dfs(s, t, INF); 197 if (tmp == 0) 198 break; 199 ret += tmp; 200 } 201 } 202 203 return ret; 204 } 205 206 void Build() { 207 int s = 0; 208 int t = maxv - 1; 209 210 rep(i, 1, sn+1) { 211 addEdge(i, t, nd[i].h); 212 } 213 214 rep(i, 1, pn+1) { 215 addEdge(s, sn+i, score[i]); 216 rep(j, 1, sn+1) { 217 if (M[i][j]) 218 addEdge(sn+i, j, INF); 219 } 220 } 221 } 222 223 int solve() { 224 int ret = 0; 225 226 rep(i, 1, pn+1) { 227 scanf("%s", s); 228 score[i] = calc(i); 229 ret += score[i]; 230 } 231 232 Build(); 233 int tmp = Dinic(0, maxv-1); 234 ret -= tmp; 235 #ifndef ONLINE_JUDGE 236 printf("maxflow = %d\n", tmp); 237 #endif 238 239 return ret; 240 } 241 242 int main() { 243 ios::sync_with_stdio(false); 244 #ifndef ONLINE_JUDGE 245 freopen("data.in", "r", stdin); 246 freopen("data.out", "w", stdout); 247 #endif 248 249 int t; 250 int ans; 251 252 scanf("%d", &t); 253 rep(tt, 1, t+1) { 254 init(); 255 scanf("%d %d", &sn, &pn); 256 rep(i, 1, sn+1) { 257 scanf("%d %d %s", &nd[i].l, &nd[i].h, nd[i].s); 258 nd[i].len = strlen(nd[i].s); 259 nd[i].getnext(); 260 } 261 ans = solve(); 262 printf("Case %d: %d\n", tt, ans); 263 } 264 265 #ifndef ONLINE_JUDGE 266 printf("time = %d.\n", (int)clock()); 267 #endif 268 269 return 0; 270 }

?

轉載于:https://www.cnblogs.com/bombe1013/p/5068586.html

總結

以上是生活随笔為你收集整理的【HDOJ】3505 Writing Robot的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。