题解 CF1214D 【Treasure Island】

来一个网络流做法 这题应该是一个很基础的模型 就是求割点，对于每个点拆成入点和出点，然后出点和入点连一条权值为$1$的边($(1,1)$和$(n,m)$连一条权值$inf$的边) 然后求最小割即可 因为答案最大是$2$,所以最多增广$2$次，因此复杂度就是$O(n*m)$的，不过常数有点大 ``` #include<bits/stdc++.h> using namespace std; #define MAXN 3000005 #define INF 0x3f3f3f3f int st = 1; int n,m; string s[MAXN]; int qsz(int i,int j) { return 2*((i-1)*m+j+1); } void rd() { cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> s[i]; } namespace mp { int n,m; struct bian { int x,y,l,ls; }b[MAXN*6]; int t[MAXN],cnt = 1; int p[MAXN]; queue<int>q; int ss,tt; void wt() { for(int i = 1; i <= cnt; i ++) if(b[i].l != 0) { cout<<b[i].x<<" "<<b[i].y<<" "<<b[i].l<<"\n"; } cout<<"------\n"; } void qk() { memset(t,0,sizeof(t)); cnt = 1; } void jb(int x,int y,int l) { cnt ++; b[cnt].x = x; b[cnt].y = y; b[cnt].l = l; b[cnt].ls = t[x]; t[x] = cnt; } void jn(int x,int y,int l) { jb(x,y,l); jb(y,x,0); } void huanyuan() { for(int i = 2; i <= m; i ++) { if((i&1) == 0) { b[i].l += b[i^1].l; b[i^1].l = 0; } } } int bfs() { memset(p,0,sizeof(p)); q.push(ss); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = t[x]; i != 0; i = b[i].ls) if(b[i].l > 0){ int y = b[i].y; if(!p[y]) { p[y] = i^1; q.push(y); } } } int x = tt,fl = INF; if(p[tt] == 0) return 0; while(x != ss) { fl = min(fl,b[p[x]^1].l); x = b[p[x]].y; } x = tt; while(x != ss) { b[p[x]^1].l -= fl; b[p[x]].l += fl; x = b[p[x]].y; } return fl; } int EK(int sb,int tb) { ss = sb; tt = tb; m = cnt; int ans = 0; while(1) { int x = bfs(); if(x == 0) break; ans += x; } huanyuan(); return ans; } } int an = 0; int main() { rd(); for(int i = 1; i <= n; i ++) for(int j = 0; j <= m-1; j++) { int t = qsz(i,j); int td = qsz(i+1,j),tr = qsz(i,j+1); if(s[i][j] != '#') { int ty = 1; if(i == 1 && j == 0) ty = 19260817; if(i == n && j == m-1) ty = 19260817; mp::jn(t,t+1,ty); mp::jn(t+1,td,19260817); mp::jn(t+1,tr,19260817); } } cout<<mp::EK(qsz(1,0),qsz(n,m-1)+1); return 0; } ``` 吐槽： 这场pretest真水。 我有个同学写了边的最小割，结果过了pretest