interlinkage:
https://ac.nowcoder.com/acm/contest/847/F
description:
solution:
- 最大权闭合子图;
- 每个单元格看成一个正权点,每一行每一列分别看成一个负权点。各自的点权就是其对应获得或者是消耗的能量(获得为正,消耗为负);
- 每个单元格向所在行对应的点连inf边,所在列对应的点连inf边,表示选择这个单元格就必须选择其所在行和所在列;
- 对于每一个关联奖励,新建一个点权为k的点。新建点向四个对应的行,列节点连inf边;
- 源点向所有正权点连边,边权为正权点的权值。所有负权点向汇点连边,边权为负权点的权值的绝对值;
- 答案=正权点权值之和-最小割;
code:
#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<queue> using namespace std; const int N=1e6+15; const int inf=1e9+7; int n,m,tot=1,S,T; int head[N],cur[N],dep[N]; struct EDGE { int to,nxt,cap; }edge[N<<1]; inline int read() { char ch=getchar();int s=0,f=1; while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return s*f; } void add(int u,int v,int w) { edge[++tot]=(EDGE){v,head[u],w};head[u]=tot; edge[++tot]=(EDGE){u,head[v],0};head[v]=tot; } int getid(int x,int y) { return (x-1)*n+y+2*n; } queue <int> q; int bfs() { memset(dep,0,sizeof(dep)); while (!q.empty()) q.pop(); dep[S]=1; q.push(S); while (!q.empty()) { int k=q.front();q.pop(); for (int i=head[k];i;i=edge[i].nxt) { int y=edge[i].to; if (!dep[y]&&edge[i].cap) { dep[y]=dep[k]+1; q.push(y); } } } return dep[T]; } int dfs(int x,int a) { if (!a||x==T) return a; int f,flow=0; for (int &i=cur[x];i;i=edge[i].nxt) { int y=edge[i].to; if (dep[y]==dep[x]+1&&(f=dfs(y,min(edge[i].cap,a)))>0) { edge[i].cap-=f; edge[i^1].cap+=f; flow+=f; a-=f; if (!a) break; } } return flow; } int dinic() { int ans=0; while (bfs()) { memcpy(cur,head,sizeof(head)); ans+=dfs(S,inf); } return ans; } int main() { n=read();m=read(); S=0;T=n*n+2*n+1; int sum=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { int c=read(),now=getid(i,j); sum+=c; add(S,now,c); add(now,i,inf); add(now,j+n,inf); } for (int i=1;i<=n;i++) add(i,T,read()); for (int i=1;i<=n;i++) add(i+n,T,read()); for (int i=1;i<=m;i++) { int i1=read(),j1=read(),i2=read(),j2=read(),k=read(); sum+=k; add(S,T+i,k); add(T+i,i1,inf);add(T+i,j1+n,inf); add(T+i,i2,inf);add(T+i,j2+n,inf); } printf("%d\n",sum-dinic()); return 0; }