题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1565
可以发现点(i,j+1)保护点(i,j)，然后加上题目给的保护关系连边。拓扑排序搞出所有合法的方案，然后就是最大权闭合子图辣。
#include<cstring> #include<iostream> #include<cstdio> #include<algorithm> #include<queue> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 600500 #define ll long long #define inf int(1e9) using namespace std; struct data{int obj,pre,c; }e[maxn*2],ed[maxn*2]; int head[maxn],d[maxn],head2[maxn],a[maxn],del[maxn],uu[maxn],q[maxn]; int tot,tot2=1,n,m,t,top,ans; void insert(int x,int y,ll z){ e[++tot].obj=y; e[tot].pre=head[x]; head[x]=tot; e[tot].c=z; } void insert2(int x,int y,int z){ ed[++tot2].obj=y; ed[tot2].pre=head2[x]; head2[x]=tot2; ed[tot2].c=z; ed[++tot2].obj=x; ed[tot2].pre=head2[y]; head2[y]=tot2; ed[tot2].c=0; } int p(int x,int y){ return (x-1)*m+y; } int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)){x=x*10+ch-'0'; ch=getchar();} return x*f; } void insert(int x,int y){ d[y]++; e[++tot].obj=y; e[tot].pre=head[x]; head[x]=tot; } void dfs(int u){ del[u]=1; for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; if (!del[v]) dfs(v); } } bool bfs(){ queue<int> q; q.push(0); clr(uu,-1); uu[0]=0; while (!q.empty()){ int u=q.front(); q.pop(); for (int j=head2[u];j;j=ed[j].pre){ int v=ed[j].obj; if (ed[j].c>0&&uu[v]==-1){ uu[v]=uu[u]+1; q.push(v); } } } if (uu[t]==-1) return 0; return 1; } int dfs(int x,int mx){ if (x==t||mx==0) return mx; int used=0; for (int j=head2[x];j;j=ed[j].pre){ int v=ed[j].obj; if (uu[v]==uu[x]+1&&ed[j].c>0){ int w=dfs(v,min(ed[j].c,mx-used)); if (w<=0) {uu[v]=-1; continue;} ed[j].c-=w; ed[j^1].c+=w; used+=w; if (used==mx) return used; } } return used; } int dinic(){ int ans=0; while (bfs()){ ans+=dfs(0,inf); } return ans; } int main(){ n=read(); m=read(); rep(i,1,n) rep(j,1,m) { a[p(i,j)]=read(); int s=read(); rep(k,1,s){ int x=read(),y=read(); x++; y++; insert(p(i,j),p(x,y)); } } rep(i,1,n) down(j,m,2) insert(p(i,j),p(i,j-1)); rep(i,1,n) rep(j,1,m) if (!d[p(i,j)]) q[++top]=p(i,j); else del[p(i,j)]=1; while (top){ int u=q[top--]; for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; d[v]--; if (!d[v]) q[++top]=v,del[v]=0; } } rep(i,1,n*m) if (del[i]) dfs(i); t=n*m+1; rep(i,1,n*m) if (!del[i]){ if (a[i]>=0) insert2(i,t,a[i]),ans+=a[i]; else insert2(0,i,-a[i]); for (int j=head[i];j;j=e[j].pre){ int v=e[j].obj; if (!del[v]) insert2(i,v,inf); } } printf("%d ",ans-dinic()); return 0; }