题意

题面

题解

很裸的一个最大权闭合子图啊。。
如果依赖关系有环，活着说他的依赖关系和环有关，就把这个点废掉。。
然后你就构图跑最大权闭合子图就好了

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=23*33;
const int MAX=1<<30;
struct qt
{int ooo;//得分 int w;int X[N],Y[N];//攻击范围
}s[N];
struct qy
{int x,y,last,z;
}ss[N*N];//指向的是他需要谁
int num,Last[N];
int n,m;
int P (int x,int y){
   return (x-1)*m+y;}
void Init (int x,int y)
{num++;ss[num].x=x;ss[num].y=y;ss[num].last=Last[x];Last[x]=num;
}
int dfn[N],low[N],belong[N],cnt,sta[N],lalal,shen;
bool in[N];
int TT[N];
int mymin (int x,int y){
   return x<y?x:y;}
int mymax(int x,int y){
   return x>y?x:y;}
void dfs1 (int x)
{dfn[x]=low[x]=++lalal;sta[++cnt]=x;in[x]=true;for (int u=Last[x];u!=-1;u=ss[u].last){int y=ss[u].y;if (dfn[y]==-1){dfs1(y);low[x]=mymin(low[x],low[y]);}else if (in[y]) low[x]=mymin(dfn[y],low[x]);}if (low[x]==dfn[x]){shen++;TT[shen]=0;int now;do{now=sta[cnt--];belong[now]=shen;in[now]=false;TT[shen]++;}while (now!=x);}
}
qy e[N*N*2];
int last[N];
int st,ed;
void init (int x,int y,int z)
{num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;swap(x,y);z=0;num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
int h[N];
bool Bt ()
{memset(h,-1,sizeof(h));h[st]=1;queue<int> q;q.push(st);while (!q.empty()){int x=q.front();q.pop();for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (e[u].z>0&&h[y]==-1){h[y]=h[x]+1;q.push(y);}}}return h[ed]!=-1;
}
int dfs (int x,int f)
{if (x==ed) return f;int s1=0;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (e[u].z>0&&h[y]==h[x]+1&&s1<f){int lalal=dfs(y,mymin(e[u].z,f-s1));s1+=lalal;e[u].z-=lalal;e[u^1].z+=lalal;}}if (s1==0) h[x]=-1;return s1;
}
int ok[N];//这个点能不能用 
//-1不知道 0不能 1能 
void dfs (int x)
{if (ok[x]!=-1) return ;for (int u=Last[x];u!=-1;u=ss[u].last){int y=ss[u].y;dfs(y);if (ok[y]==0){ok[x]=0;return ;}}ok[x]=1;
}
void solve ()
{shen=lalal=cnt=0;memset(dfn,-1,sizeof(dfn));memset(in,false,sizeof(in));for (int u=1;u<=m*n;u++)if (dfn[u]==-1)dfs1(u);memset(ok,-1,sizeof(ok));for (int u=1;u<=n*m;u++)if (TT[belong[u]]>1)ok[u]=0;for (int u=1;u<=n*m;u++)if (ok[u]==-1)dfs(u);num=1;memset(last,-1,sizeof(last));st=n*m+1;ed=st+1;int ans=0;for (int u=1;u<=n*m;u++)if (ok[u]==1){if (s[u].ooo>0) init(st,u,s[u].ooo),ans=ans+s[u].ooo;else init(u,ed,-s[u].ooo);for (int i=Last[u];i!=-1;i=ss[i].last){int y=ss[i].y;init(u,y,MAX);}}while (Bt()) ans=ans-dfs(st,MAX);printf("%d\n",ans);
}
void Ins ()
{num=0;memset(Last,-1,sizeof(Last));scanf("%d%d",&n,&m);for (int u=1;u<=n;u++)for (int i=1;i<=m;i++){int x=P(u,i);scanf("%d",&s[x].ooo);scanf("%d",&s[x].w);for (int j=1;j<=s[x].w;j++){int xx,yy;scanf("%d%d",&xx,&yy);xx++;yy++;Init(P(xx,yy),x);}if (i!=m) Init(P(u,i),P(u,i+1));}/*for (int u=1;u<=num;u++)printf("%d %d\n",ss[u].x,ss[u].y);*/
}int main()
{Ins();solve();return 0;
}