題解

我一直也不會網絡流……orz

我們分析下這道題，顯然和行列沒啥關系，就是想給你n + m個串

那么我們對于非回文單詞之外的單詞，找到兩兩匹配的反轉單詞（即使另一個反轉單詞不會出現也要建出來）

具體就是我們建一個hash表，遇見一個單詞讀進來，把這個單詞反轉之后再存進哈希表里

然后我們把一對反轉單詞挑出來，按照字典序，字典序小的往字典序大的連一條流量為2的邊

那么現在我們考慮一下加入閱讀方式都已經被全部確定，那么網絡流的建圖方式就應該是
如果順著給定的順序是字典序較小的，那么就向給定循序讀的單詞連一條正無窮的邊
如果順著給定順序是字典序較大的，那么給定順序讀出的單詞就向這一行或一列連一條正無窮的邊

跑最大流就是答案

現在我們有了未知順序的邊，那么我們就要求了某些單詞（這里正反單詞算一種）必須全是以字典序較小的方式讀，或者全是以字典序較大的方式讀

這個限制可以用最大流等于最小割，可以想一下
如果我們需要反轉部分在某些串里字典序較小的單詞，從而使整個0串全是字典序較大的單詞，那么這些串所連的單詞所在的邊就會滿流
同理，如果反轉字典序較大的單詞，靠近匯點的一邊單詞會滿流
因為最大流等于最小割，所以總會選擇較小的一邊流滿

所以我們的連邊方式就是0串所有單詞的字典序較大的一邊向0串連正無窮邊，0串向所有單詞字典序較小的一邊連正無窮的邊

跑一遍最大流加上回文單詞個數就是答案了

我的代碼怎么又將近寫了8K= =

代碼

#include <bits/stdc++.h> #define enter putchar('\n') #define space putchar(' ') #define pii pair<int,int> #define fi first #define se second #define mp make_pair #define MAXN 1000005 #define mo 999999137 #define pb push_back //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) out(x / 10);putchar('0' + x % 10); } int N,M; char s[105][105]; int H[105],L[105]; int e[105]; struct Word{char s[75];int hsh;friend bool operator < (const Word &a,const Word &b) {return a.hsh < b.hsh;}friend bool operator == (const Word &a,const Word &b) {return a.hsh == b.hsh;} }C[10005]; int op[10005],revcnt; bool rev[10005],isSmall[10005]; struct node {int to,next,cap; }E[100005]; int sumE,head[10005],cnt,S,T; int last[10005],dis[10005],gap[10005]; map<int,int> hash_list; vector<int> W; void add(int u,int v,int c) {E[++sumE].to = v;E[sumE].next = head[u];E[sumE].cap = c;head[u] = sumE; } void addtwo(int u,int v,int c) {add(u,v,c);add(v,u,0); } int calc(char *s,int len) {int res = 0;for(int i = 1 ; i <= len ; ++i) {res = (res + 1LL * e[i - 1] * (s[i] - 'A' + 1) % mo) % mo;}return res; } void Insert(int id,char *t,int len) {t[len + 1] = '\0';memcpy(C[id].s,t,sizeof(char) * (len + 2));C[id].hsh = calc(t,len); }bool cmp(char *s,char *t,int len) {for(int i = 1 ; i <= len ; ++i) {if(s[i] != t[i]) return s[i] < t[i];}return 0; } int sap(int u,int aug) {if(u == T) return aug;int flow = 0;for(int i = last[u] ; i ; i = E[i].next) {int v = E[i].to;if(dis[v] + 1 == dis[u]) {int t = sap(v,min(aug - flow,E[i].cap));flow += t;E[i].cap -= t;E[i ^ 1].cap += t;if(aug == flow) return flow;if(dis[S] >= T) return flow;}}--gap[dis[u]];if(!gap[dis[u]]) dis[S] = T;++gap[++dis[u]];last[u] = head[u];return flow; } void Init() {read(N);read(M);for(int i = 1 ; i <= N ; ++i) read(H[i]);for(int i = 1 ; i <= M ; ++i) read(L[i]);for(int i = 1 ; i <= N ; ++i) scanf("%s",s[i] + 1);memset(head,0,sizeof(head));sumE = 1;hash_list.clear();memset(rev,0,sizeof(rev));revcnt = 0;memset(isSmall,0,sizeof(isSmall));memset(dis,0,sizeof(dis));memset(gap,0,sizeof(gap));} void Solve() {Init();char tmp[75];memset(tmp,0,sizeof(tmp));int tot = 0;cnt = 0;for(int i = 1 ; i <= N ; ++i) {tot = 0;for(int j = 1 ; j <= M ; ++j) {if(s[i][j] == '_') {if(tot) {Insert(++cnt,tmp,tot);reverse(tmp + 1,tmp + tot + 1);Insert(++cnt,tmp,tot);}tot = 0;}else tmp[++tot] = s[i][j];}if(tot) {Insert(++cnt,tmp,tot);reverse(tmp + 1,tmp + tot + 1);Insert(++cnt,tmp,tot);}}for(int j = 1 ; j <= M ; ++j) {tot = 0;for(int i = 1 ; i <= N ; ++i) {if(s[i][j] == '_') {if(tot) {Insert(++cnt,tmp,tot);reverse(tmp + 1,tmp + tot + 1);Insert(++cnt,tmp,tot);}tot = 0;}else tmp[++tot] = s[i][j];}if(tot) {Insert(++cnt,tmp,tot);reverse(tmp + 1,tmp + tot + 1);Insert(++cnt,tmp,tot);}}sort(C + 1,C + cnt + 1);cnt = unique(C + 1,C + cnt + 1) - C - 1;for(int i = 1 ; i <= cnt ; ++i) {hash_list[C[i].hsh] = i;}for(int i = 1 ; i <= cnt ; ++i) {memcpy(tmp,C[i].s,sizeof(tmp));int l = strlen(tmp + 1);reverse(tmp + 1,tmp + l + 1);if(calc(tmp,l) == C[i].hsh) {op[i] = i;rev[i] = 1;++revcnt;}else if(cmp(C[i].s,tmp,l)) {op[i] = hash_list[calc(tmp,l)];op[op[i]] = i;isSmall[i] = 1;isSmall[op[i]] = 0;addtwo(i,op[i],2);}}S = cnt + N + M + 1;T = S + 1;for(int i = 1 ; i <= N ; ++i) {W.clear();tot = 0;for(int j = 1 ; j <= M ; ++j) {if(s[i][j] == '_') {if(tot) {int t = hash_list[calc(tmp,tot)];if(!rev[t]) W.pb(t);}tot = 0;}else tmp[++tot] = s[i][j];}if(tot) {int t = hash_list[calc(tmp,tot)];if(!rev[t]) W.pb(t);}if(!W.size()) continue;sort(W.begin(),W.end());W.erase(unique(W.begin(),W.end()),W.end());int siz = W.size();if((H[i] == 1 && isSmall[W[0]]) || (H[i] == -1 && !isSmall[W[0]])) {addtwo(S,cnt + i,0x7fffffff);for(int j = 0 ; j < siz ; ++j) {if(isSmall[W[j]]) addtwo(cnt + i,W[j],0x7fffffff);else addtwo(cnt + i,op[W[j]],0x7fffffff);}}else if((H[i] == 1 && !isSmall[W[0]]) || (H[i] == -1 && isSmall[W[0]])) {addtwo(cnt + i,T,0x7fffffff);for(int j = 0 ; j < siz ; ++j) {if(!isSmall[W[j]]) addtwo(W[j],cnt + i,0x7fffffff);else addtwo(op[W[j]],cnt + i,0x7fffffff);}}else if(H[i] == 0) {if(!isSmall[W[0]]) {for(int j = 0 ; j < siz ; ++j) {W[j] = op[W[j]];}}for(int j = 0 ; j < siz ; ++j) {addtwo(cnt + i,W[j],0x7fffffff);addtwo(op[W[j]],cnt + i,0x7fffffff);}}}for(int j = 1 ; j <= M ; ++j) {W.clear();tot = 0;for(int i = 1 ; i <= N ; ++i) {if(s[i][j] == '_') {if(tot) {int t = hash_list[calc(tmp,tot)];if(!rev[t]) W.pb(t);}tot = 0;}else tmp[++tot] = s[i][j];}if(tot) {int t = hash_list[calc(tmp,tot)];if(!rev[t]) W.pb(t);}if(!W.size()) continue;sort(W.begin(),W.end());W.erase(unique(W.begin(),W.end()),W.end());int siz = W.size();if((L[j] == 1 && isSmall[W[0]]) || (L[j] == -1 && !isSmall[W[0]])) {addtwo(S,cnt + N + j,0x7fffffff);for(int i = 0 ; i < siz ; ++i) {if(isSmall[W[i]]) addtwo(cnt + N + j,W[i],0x7fffffff);else addtwo(cnt + N + j,op[W[i]],0x7fffffff);}}else if((L[j] == 1 && !isSmall[W[0]]) || (L[j] == -1 && isSmall[W[0]])) {addtwo(cnt + N + j,T,0x7fffffff);for(int i = 0 ; i < siz ; ++i) {if(!isSmall[W[i]]) addtwo(W[i],cnt + N + j,0x7fffffff);else addtwo(op[W[i]],cnt + N + j,0x7fffffff);}}else if(L[j] == 0) {if(!isSmall[W[0]]) {for(int i = 0 ; i < siz ; ++i) {W[i] = op[W[i]];}}for(int i = 0 ; i < siz ; ++i) {addtwo(cnt + N + j,W[i],0x7fffffff);addtwo(op[W[i]],cnt + N + j,0x7fffffff);}}}for(int i = 1 ; i <= T ; ++i) last[i] = head[i];int ans = revcnt;while(dis[S] < T) ans += sap(S,0x7fffffff);out(ans);enter; } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endife[0] = 1;for(int i = 1 ; i <= 100 ; ++i) e[i] = e[i - 1] * 47 % mo;int T;read(T);while(T--) {Solve();}return 0; }

轉載于:https://www.cnblogs.com/ivorysi/p/9522138.html

總結

以上是生活随笔為你收集整理的【LOJ】#2066. 「SDOI2016」墙上的句子的全部內容，希望文章能夠幫你解決所遇到的問題。

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