我: “立個flag 14點之前調完這題”

洛谷AC時間: 2019-06-24 14:00:16

實力打臉。。。

網絡流板子從來寫不對系列

題目鏈接: (BZOJ) https://www.lydsy.com/JudgeOnline/problem.php?id=1565

(luogu) https://www.luogu.org/problemnew/show/P2805

題解: 長得就那么像個最大權閉合子圖啊。。。

\(i\)攻擊\(j\)相當于如果想吃掉\(i\)必須吃掉\(j\), 另外如果吃掉\(i\)必須吃掉\(i\)右側的點，最大權閉合子圖。

但是可能有環，注意環并非要么全吃要么全不吃而是全都不能吃，所以用Tarjan提前判一下環，在環里的點和\(T\)連\(+\inf\)表示不能吃

時間復雜度\(O(MaxFlow(nm,(nm)^2))\).

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std;const int N = 602; const int M = 362400; const int INF = 1e8;namespace MaxFlow {struct Edge{int v,w,nxt,rev;} e[(M<<1)+3];int fe[N+3];int te[N+3];int dep[N+3];int que[N+3];int n,en;void addedge(int u,int v,int w){en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;en++; e[en].v = u; e[en].w = 0;e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;}bool bfs(){for(int i=1; i<=n; i++) dep[i] = 0;int head = 1,tail = 1; que[tail] = 1; dep[1] = 1;while(head<=tail){int u = que[head]; head++;for(int i=fe[u]; i; i=e[i].nxt){if(dep[e[i].v]==0 && e[i].w>0){dep[e[i].v] = dep[u]+1;tail++; que[tail] = e[i].v;}}}return dep[2]!=0;}int dfs(int u,int cur){if(u==2) {return cur;}int rst = cur;for(int i=te[u]; i; i=e[i].nxt){if(dep[e[i].v]==dep[u]+1 && e[i].w>0 && rst>0){int flow = dfs(e[i].v,min(rst,e[i].w));if(flow>0){e[i].w-=flow; e[e[i].rev].w += flow; rst-=flow;if(e[i].w>0) {te[u] = i;}if(rst==0) {return cur;}}}}if(cur==rst) {dep[u] = 0;}return cur-rst;}int dinic(int _n){n = _n;int ret = 0;while(bfs()){for(int i=1; i<=n; i++) te[i] = fe[i];ret += dfs(1,INF);}return ret;} }namespace Tarjan {struct Edge{int v,nxt;} e[M+3];int fe[N+3];int dfn[N+3],low[N+3],stk[N+3];bool instk[N+3];bool inscc[N+3];int n,en,cnt,tp;void addedge(int u,int v){en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en;}void dfs(int u){cnt++; dfn[u] = low[u] = cnt; tp++; stk[tp] = u; instk[u] = true;for(int i=fe[u]; i; i=e[i].nxt){if(!dfn[e[i].v]){dfs(e[i].v);low[u] = min(low[u],low[e[i].v]);}else if(instk[e[i].v]){low[u] = min(low[u],low[e[i].v]);}}if(low[u]>=dfn[u]){if(stk[tp]!=u) {inscc[u] = true;}while(stk[tp]!=u){inscc[stk[tp]] = true;instk[stk[tp]] = false;stk[tp] = 0; tp--;}stk[tp] = 0; tp--; instk[u] = false;}}void work(int _n){n = _n;for(int i=1; i<=n; i++){if(!dfn[i]) {dfs(i);}}} }int n,m;int getid(int x,int y) {return x*m+y+3;}int main() {scanf("%d%d",&n,&m); int ans = 0;for(int i=1; i<=n*m; i++){int x; scanf("%d",&x);if(x>0) {MaxFlow::addedge(1,i+2,x); ans += x;}else if(x<0) {MaxFlow::addedge(i+2,2,-x);}scanf("%d",&x);while(x--){int y,z; scanf("%d%d",&y,&z); int pos = getid(y,z);MaxFlow::addedge(pos,i+2,INF);Tarjan::addedge(pos-2,i);}if(i%m!=0){MaxFlow::addedge(i+2,i+3,INF);Tarjan::addedge(i,i+1);}}Tarjan::work(n*m);for(int i=1; i<=n*m; i++){if(Tarjan::inscc[i]){MaxFlow::addedge(i+2,2,INF);}}int tmp = MaxFlow::dinic(n*m+2);ans -= tmp;printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 1565 Luogu P2805 [NOI2009]植物大战僵尸 (Tarjan判环、最小割)的全部內容，希望文章能夠幫你解決所遇到的問題。

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