题意

链接

分析

首先按照题目给出的保护关系可以建出来一个DAG，然后就是裸的最大权闭合子图了。但不难发现会出现环的情况，所以要先把图反向然后把不能拓扑排序的点给去掉就好了。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=605; const int inf=0x3f3f3f3f; int n,m,cnt,last[N],ls[N],val[N],d[N]; bool vis[N]; queue<int> que; struct edge{int to,next;}e[N*N*2]; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int point(int x,int y) { return (x-1)*m+y; } void addedge(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=ls[v];ls[v]=cnt; } struct Max_flow { int cnt,last[N],s,t,cur[N],dis[N]; struct edge{int to,next,c;}e[N*N*2]; void addedge(int u,int v,int c) { e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt; } bool bfs() { for (int i=s;i<=t;i++) dis[i]=0; while (!que.empty()) que.pop(); dis[s]=1;que.push(s); while (!que.empty()) { int u=que.front();que.pop(); for (int i=last[u];i;i=e[i].next) if (e[i].c&&!dis[e[i].to]) { dis[e[i].to]=dis[u]+1; if (e[i].to==t) return 1; que.push(e[i].to); } } return 0; } int dfs(int x,int maxf) { if (x==t||!maxf) return maxf; int ret=0; for (int &i=cur[x];i;i=e[i].next) if (e[i].c&&dis[e[i].to]==dis[x]+1) { int f=dfs(e[i].to,min(e[i].c,maxf-ret)); e[i].c-=f; e[i^1].c+=f; ret+=f; if (maxf==ret) break; } return ret; } int dinic() { int ans=0; while (bfs()) { for (int i=s;i<=t;i++) cur[i]=last[i]; ans+=dfs(s,inf); } return ans; } }flow; int main() { n=read();m=read(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { val[point(i,j)]=read(); int w=read(); while (w--) { int x=read()+1,y=read()+1; addedge(point(i,j),point(x,y)); d[point(x,y)]++; } if (j>1) addedge(point(i,j),point(i,j-1)),d[point(i,j-1)]++; } for (int i=1;i<=n*m;i++) if (!d[i]) que.push(i); while (!que.empty()) { int u=que.front();que.pop();vis[u]=1; for (int i=last[u];i;i=e[i].next) { d[e[i].to]--; if (!d[e[i].to]) que.push(e[i].to); } } int ans=0;flow.s=0;flow.t=n*m+1;flow.cnt=1; for (int i=1;i<=n*m;i++) if (vis[i]) { if (val[i]>0) ans+=val[i],flow.addedge(flow.s,i,val[i]); else flow.addedge(i,flow.t,-val[i]); for (int j=ls[i];j;j=e[j].next) if (vis[e[j].to]) flow.addedge(i,e[j].to,inf); } ans-=flow.dinic(); printf("%d",ans); return 0; }