本文共 2400 字，大约阅读时间需要 8 分钟。

题意

题解

很裸的一个最大权闭合子图啊。。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        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;}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
         
           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
          
           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;}