[BZOJ1565][NOI2009]植物大战僵尸（tarjan+最小割）

2019-11-06 07:32:35

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

首先有一些保护与被保护的关系是给出的，还有就是每一排前面的点可以保护后面的点从保护的点向被保护的点连边可以发现，如果一个强连通分量的大小大于1，那么这个强连通分量里的所有点都不可能被打到。并且如果有一个点不可能被打到，它能到达的点也都不可能被打到把不可能被打到的点都剔除出去，最后只可能剩下一个DAG 那么这些点是可以选择的，但是选择某一个点的前提是，所有保护它的点都被选择权值有正有负，就是一个非常典型的最大权闭合子图问题了，建模时候跑最小割就行了

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<queue>using namespace std;#define inf 2100000000#define N 1005int n,m,dfs_clock,scc,maxflow,ans,s,t;int tot,point[N],nxt[N*N],v[N*N];int score[N],dfn[N],low[N],stack[N],tmp,belong[N],cnt[N];bool vis[N];void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void tarjan(int x){ dfn[x]=low[x]=++dfs_clock;stack[++tmp]=x;vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!dfn[v[i]]) { tarjan(v[i]); low[x]=min(low[x],low[v[i]]); } else if (vis[v[i]]) low[x]=min(low[x],dfn[v[i]]); if (dfn[x]==low[x]) { int now=0;++scc; while (now!=x) { now=stack[tmp--]; vis[now]=0; belong[now]=scc; ++cnt[scc]; } }}void dfs(int x){ vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) dfs(v[i]);}namespace Flow{ int tot,point[N],nxt[N*N],v[N*N],remain[N*N]; int deep[N],last[N],cur[N],num[N]; queue <int> q; void clear() { tot=-1; memset(point,-1,sizeof(point)); } void addedge(int x,int y,int cap) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0; } void bfs(int t) { for (int i=1;i<=t;++i) deep[i]=t; deep[t]=0; for (int i=1;i<=t;++i) cur[i]=point[i]; q.push(t); while (!q.empty()) { int now=q.front();q.pop(); for (int i=point[now];i!=-1;i=nxt[i]) if (deep[v[i]]==t&&remain[i^1]) { deep[v[i]]=deep[now]+1; q.push(v[i]); } } } int addflow(int s,int t) { int now=t,ans=inf; while (now!=s) { ans=min(ans,remain[last[now]]); now=v[last[now]^1]; } now=t; while (now!=s) { remain[last[now]]-=ans; remain[last[now]^1]+=ans; now=v[last[now]^1]; } return ans; } void isap(int s,int t) { bfs(t); for (int i=1;i<=t;++i) ++num[deep[i]]; int now=s; while (deep[s]<t) { if (now==t) { maxflow+=addflow(s,t); now=s; } bool has_find=0; for (int i=cur[now];i!=-1;i=nxt[i]) if (deep[v[i]]+1==deep[now]&&remain[i]) { has_find=1; cur[now]=i; last[v[i]]=i; now=v[i]; break; } if (!has_find) { int minn=t-1; for (int i=point[now];i;i=nxt[i]) if (remain[i]) minn=min(minn,deep[v[i]]); if (!(--num[deep[now]])) break; ++num[deep[now]=minn+1]; cur[now]=point[now]; if (now!=s) now=v[last[now]^1]; } } }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) for (int j=2;j<=m;++j) { int x=(i-1)*m+j; add(x,x-1); } for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) { int x=(i-1)*m+j,y,k,r,c; scanf("%d",&score[x]); scanf("%d",&k); while (k--) { scanf("%d%d",&r,&c);++r,++c; y=(r-1)*m+c; if (y!=x-1) add(x,y); } } n*=m; for (int i=1;i<=n;++i) if (!dfn[i]) tarjan(i); for (int i=1;i<=n;++i) if (cnt[belong[i]]>1&&!vis[i]) dfs(i); Flow::clear();s=n+1,t=s+1; for (int i=1;i<=n;++i) if (!vis[i]) { if (score[i]>0) Flow::addedge(s,i,score[i]),ans+=score[i]; else if (score[i]<0) Flow::addedge(i,t,-score[i]); for (int j=point[i];j;j=nxt[j]) if (!vis[v[j]]) Flow::addedge(v[j],i,inf); } Flow::isap(s,t); PRintf("%d/n",ans-maxflow);}

上一篇：蓝桥杯历届试题带分数

下一篇：golang 开发gui，还真有gui的框架，就是做个简单的行