这题数据xie强qwq。拓扑用的那个图建反了得80.
一眼看出（个屁，题解上都说一眼看出，然而我还是太蒻了）这是个最大权闭合图。从被保护植物向保护植物连边，然后跑最大流，用正点权和减去。
哦最大权闭合图我会。
准备开始码。
等等题解下面好像还写东西？
emmmm有环，所以拓扑排序……
好，我写……
写了半小时，调了两发过样例交了。
wtf80？
然后想了半小时，想不出来为什么qwq、
然后手推。
不对呀数据给的这张图拓扑不动呀？
然后想了想，觉得不对呀……应该反着拓扑才对……
然后翻题解
emm果然是在反向图上拓扑。
emmmmmm
于是沉吟良久改了四句话，然后就A了。
qwqqqqqq。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<algorithm> #include<queue> #define maxn 12000 #define maxm 1000000 using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int n,m; inline int count(int i){ return i&1?i+1:i-1; } inline int calc(int i,int j){ return (i-1)*m+j; } int dfn[maxn]; bool vis[maxn]; int list[maxn]; int Start,End; int indl[maxn]; bool ext[maxn]; queue<int>f; struct Pic{ struct Edge{ int next,to,val; }edge[maxm]; int head[maxn],num; Pic(){memset(head,0,sizeof(head)); num=0; } inline void addedge(int from,int to,int val){ edge[++num]=(Edge){head[from],to,val}; head[from]=num; } inline void add(int from,int to,int val){ addedge(from,to,val); addedge(to,from,0); } bool bfs(){ memset(vis,0,sizeof(vis)); dfn[Start]=1; vis[Start]=1; queue<int>q; q.push(Start); while(!q.empty()){ int from=q.front(); q.pop(); for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(vis[to]||edge[i].val==0) continue; vis[to]=1; dfn[to]=dfn[from]+1; q.push(to); } } return vis[End]; } int dfs(int x,int val){ if(x==End||val==0) return val; int flow=0; vis[x]=1; for(int i=head[x];i;i=edge[i].next){ int to=edge[i].to; if(edge[i].val==0||dfn[to]!=dfn[x]+1) continue; int now=dfs(to,min(val,edge[i].val)); edge[i].val-=now; edge[count(i)].val+=now; val-=now; flow+=now; if(val<=0) break; } if(val!=flow) dfn[x]=-1; return flow; } inline int maxflow(){ int ans=0; while(bfs()){ memset(vis,0,sizeof(vis)); for(int i=Start;i<=End;++i) list[i]=head[i]; int now=dfs(Start,0x7fffffff); if(now==0) break; ans+=now; } return ans; } }Old,New; int sco[200][200]; int sum; int main(){ n=read(),m=read(); for(int i=1;i<=n;++i) for(int j=1;j<m;++j){ int x=calc(i,j+1); Old.addedge(x,calc(i,j),0); indl[calc(i,j)]++; //Old.addedge(calc(i,j),x,0); //indl[x]++; } for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ sco[i][j]=read(); int x=read(); for(int k=1;k<=x;++k){ int a=read()+1,b=read()+1; int opt=calc(a,b); Old.addedge(calc(i,j),opt,0); indl[opt]++; //Old.addedge(opt,calc(i,j),0); //indl[calc(i,j)]++; } } for(int i=1;i<=n*m;++i) if(indl[i]==0){ f.push(i); ext[i]=1; } while(!f.empty()){ int from=f.front(); f.pop(); for(int i=Old.head[from];i;i=Old.edge[i].next){ int to=Old.edge[i].to; indl[to]--; if(indl[to]==0){ ext[to]=1; f.push(to); } } } End=n*m+1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ int ret=calc(i,j); if(ext[ret]==0) continue; if(sco[i][j]>0) sum+=sco[i][j]; if(sco[i][j]>0) New.add(Start,ret,sco[i][j]); else New.add(ret,End,-sco[i][j]); for(int k=Old.head[ret];k;k=Old.edge[k].next){ int to=Old.edge[k].to; New.add(to,ret,0x7fffffff); } } int ans=New.maxflow(); printf("%d",sum-ans); return 0; }