Editorial for Thu hoạch
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <cstring> using namespace std; int m,n,sm,cnt,last,c[20010],d[20010],low[20010],num[20010],st[20010]; int f[20010],val[20010],vs[20010]; vector <int> a[20010],b[20010]; char s[10011]; void visit(int x) { low[x]=num[x]=++cnt; st[++last]=x; for (int i=0;i<int(a[x].size());i++) { int y=a[x][i]; if (!d[y]) { if (num[y]) low[x]=min(low[x],num[y]); else { visit(y); low[x]=min(low[x],low[y]); } } } if (low[x]!=num[x]) return; sm++; while (1) { int i=st[last--]; d[i]=sm; val[sm]+=c[i]; if (i==x) return; } } void calc(int x) { vs[x]=1; for (int i=0;i<int(b[x].size());i++) { int y=b[x][i]; if (!vs[y]) calc(y); f[x]=max(f[x],f[y]); } f[x]+=val[x]; } int main() { //freopen("in","r",stdin); char t[10100],ss[10100]; cin >> m >> n; gets(t); for (int i=1;i<=m;i++) { scanf("%s",&ss); int l=strlen(ss); for (int j=0;j<n;j++) s[j]=(j<l?ss[j]:'0'); for (int j=1;j<=n;j++) { int x=(i-1)*n+j; if (s[j-1]=='#') { d[x]=-1; continue; } if (j<n) a[x].push_back(x+1); if (i<m) a[x].push_back(x+n); if (s[j-1]>='0' && s[j-1]<='9') c[x]=s[j-1]-'0'; else { if (s[j-1]=='N' && i>1 && !d[x-n]) a[x].push_back(x-n); if (s[j-1]=='W' && j>1 && !d[x-1]) a[x].push_back(x-1); } } gets(t); } n*=m; for (int i=1;i<=n;i++) if (!d[i]) visit(i); for (int i=1;i<=n;i++) if (d[i]>0) for (int j=0;j<int(a[i].size());j++) { int y=a[i][j]; if (d[y]<0) continue; if (d[i]!=d[y]) b[d[i]].push_back(d[y]); } if (d[1]<0) cout << 0 << endl; else calc(d[1]), cout << f[d[1]] << endl; return 0; }
Code mẫu của ladpro98
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <stack> #include <climits> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) const int M = 110; const int N = M * M; const int oo = INT_MAX; using namespace std; int n, m, cnt, timer, scc; int low[N], num[N], lab[N], F[N], val[N], gain[N], ver[M][M]; bool was[N]; char ch[M][M]; vector<int> a[N], adj[N], super[N]; stack<int> S; void Tarjan(int u) { num[u] = ++timer; low[u] = oo; S.push(u); FOR(i, 0, a[u].size()) { int v = a[u][i]; if (was[v]) continue; if (num[v]) low[u] = min(low[u], num[v]); else { Tarjan(v); low[u] = min(low[u], low[v]); } } if (low[u] >= num[u]) { int v; do { v = S.top(); was[v] = true; lab[v] = scc; gain[scc] += val[v]; super[scc].push_back(v); S.pop(); } while (v != u); scc++; } } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> m >> n; REP(i, 1, m) REP(j, 1, n) ver[i][j] = ++cnt; REP(i, 1, m) REP(j, 1, n) cin >> ch[i][j]; REP(i, 1, m) REP(j, 1, n) { if (ch[i][j] == '#') continue; if (ch[i][j + 1] != '#') a[ver[i][j]].push_back(ver[i][j + 1]); if (ch[i + 1][j] != '#') a[ver[i][j]].push_back(ver[i + 1][j]); if (ch[i][j] == 'W') {if (ch[i][j - 1] != '#') a[ver[i][j]].push_back(ver[i][j - 1]);} else if (ch[i][j] == 'N') {if (ch[i - 1][j] != '#') a[ver[i][j]].push_back(ver[i - 1][j]);} else val[ver[i][j]] = ch[i][j] - '0'; } REP(i, 1, cnt) if (!was[i]) Tarjan(i); FOR(i, 0, scc) FOR(j, 0, super[i].size()) FOR(k, 0, a[super[i][j]].size()) adj[i].push_back(lab[a[super[i][j]][k]]); FOR(i, 0, scc) { F[i] = gain[i]; FOR(j, 0, adj[i].size()) if (i != adj[i][j]) F[i] = max(F[i], gain[i] + F[adj[i][j]]); } cout << F[lab[ver[1][1]]]; return 0; }
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); const int MN = 111; const int MN2 = 111*111; int m, n, now; int low[MN][MN], num[MN][MN], reg[MN][MN], nReg; int value[MN2], f[MN2], vao[MN2]; vector< pair<int,int> > ke[MN][MN]; vector<int> ke2[MN2]; pair<int,int> st[MN2]; int top; char a[MN][MN]; void init() { FOR(i,1,m) FOR(j,1,n) if (a[i][j] != '#') { if (i < m && a[i+1][j] != '#') ke[i][j].PB(MP(i+1, j)); if (j < n && a[i][j+1] != '#') ke[i][j].PB(MP(i, j+1)); if (a[i][j] == 'W' && j > 1 && a[i][j-1] != '#') ke[i][j].PB(MP(i,j-1)); if (a[i][j] == 'N' && i > 1 && a[i-1][j] != '#') ke[i][j].PB(MP(i-1,j)); } } void add(int u, int v, int r) { reg[u][v] = r; if (a[u][v] >= '0' && a[u][v] <= '9') { value[r] += a[u][v] - '0'; } } void dfs(int u, int v) { num[u][v] = ++now; low[u][v] = now; st[++top] = MP(u,v); REP(i,ke[u][v].size()) { int uu = ke[u][v][i].F, vv = ke[u][v][i].S; if (reg[uu][vv]) continue; if (num[uu][vv]) low[u][v] = min(low[u][v], num[uu][vv]); else { dfs(uu, vv); low[u][v] = min(low[u][v], low[uu][vv]); } } if (low[u][v] == num[u][v]) { ++nReg; while (st[top] != MP(u,v)) { int uu = st[top].F, vv = st[top].S; add(uu, vv, nReg); --top; } add(u, v, nReg); --top; } } void build() { FOR(i,1,m) FOR(j,1,n) if (num[i][j] == 0 && a[i][j] != '#') { dfs(i,j); } // DEBUG(nReg); // PR(value, nReg); // FOR(i,1,m) { // FOR(j,1,n) cout << reg[i][j] << ' '; // cout << endl; // } FOR(u,1,m) FOR(v,1,n) { REP(i,ke[u][v].size()) { int uu = ke[u][v][i].F, vv = ke[u][v][i].S; int r1 = reg[u][v], r2 = reg[uu][vv]; if (r1 != r2) { ke2[r1].PB(r2); vao[r2]++; } } } } int s[MN2], t, ls[MN2], cur; void dp() { FOR(i,1,nReg) if (vao[i] == 0) { s[++t] = i; } while (t) { int u = s[t--]; ls[++cur] = u; REP(i,ke2[u].size()) { int v = ke2[u][i]; --vao[v]; if (vao[v] == 0) s[++t] = v; } } FORD(t,cur,1) { int u = ls[t]; f[u] = value[u]; REP(i,ke2[u].size()) { int v = ke2[u][i]; f[u] = max(f[u], f[v] + value[u]); } } // PR(f, nReg); cout << f[reg[1][1]] << endl; } int main() { scanf("%d%d\n", &m, &n); FOR(i,1,m) { scanf("%s\n", &a[i][1]); } init(); build(); dp(); return 0; }
Comments