链接：
P1361
题意：
有 \(n\) 个点，需要将他们分成两个点集，给出每个点分别在两个点集中的贡献。同时给出 \(m\) 个规则，每个规则给出一些点，当这些点在同一个点集中时会有额外贡献，给出每个规则的点分别在两个点集中的贡献。请最大化贡献和。
分析：
（图片和思路来自洛谷博客）
最小割可以用来把一些点分成两个点集，所以考虑最小割。只需要最小化"损失的贡献"。
我们把一个点分到左边的点集，那么右边的贡献就会损失，所以不考虑额外规则时，我们可以建出这样的模型：
中间是点，左右连边的流量是对左右点集的贡献，那么最小割就是最小的"损失的贡献"。
然后考虑额外规则。
一个规则对点集的贡献有三种情况，对点集 \(S\) 贡献，对点集 \(T\) 贡献或者不贡献，这意味着我们无法通过一个状态来处理，我们可以分成两部分来考虑，对 \(S\) 的贡献和对 \(T\) 的贡献。
因为这个贡献自然不能连向已经存在的边，所以我们先连向一个虚点，单独考虑对 \(S\) 的贡献，只要有一个点被分到了点集 \(T\)，那么这个贡献就应该"损失"， 所以每个点都应该和这个虚点相连，于是：
只要有一个点被分到了点集 \(T\)，那么这个贡献就应该"损失"，所以"损失的贡献"应该在黄色边而非蓝色边上。假如点 \(c\) 被分到了点集 \(T\)，那么任意一条 \(S\) 到 \(c\) 的路径都应该断开。对于 \(S\rightarrow X\rightarrow c\) ，我们想要割掉黄色边，保留蓝色边，所以把黄色边的流量设为贡献，同时为了避免割掉蓝色边，将其流量设为
inf
。
对 \(T\) 的贡献也是一样的，所以最终的模型是：
总结一下：
基本二者取一式问题模型，也就是最小割分割点集。
虚点的应用，用来处理一些基础模型之上的规则。
算法：
建出模型跑最大流即可。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
const int N=3e3+5;
const int M=2e6+4e3+5;
const int inf=0x7fffffff;
int n,m,s,t,cnt,maxflow;
struct edge{
int v,w,nxt;
}e[M<<1];
int head[N],en=1;
void insert(int u,int v,int w){
e[++en].v=v;
e[en].w=w;
e[en].nxt=head[u];
head[u]=en;
}
void add(int u,int v,int w){
insert(u,v,w);
insert(v,u,0);
}
int cur[N],dis[N];
queue<int> q;
bool bfs(){
for(int i=1;i<=cnt;i++)
dis[i]=0,cur[i]=head[i];
while(!q.empty())q.pop();
q.push(s);dis[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v){
if(!dis[v]&&e[i].w){
dis[v]=dis[u]+1;
if(v==t)return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int in){
if(!in||u==t){return in;}
int out=0;
for(int i=cur[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v){
cur[u]=i;
if(dis[v]!=dis[u]+1||!e[i].w)continue;
int tmp=dfs(v,min(in-out,e[i].w));
e[i].w-=tmp;
e[i^1].w+=tmp;
out+=tmp;
if(in==out)break;
}
return out;
}
void dinic(){
while(bfs()){maxflow+=dfs(s,inf);}
}
int ans;
signed main(){
n=read();s=n+1,cnt=t=n+2;
for(int i=1;i<=n;i++){int tmp=read();add(s,i,tmp);ans+=tmp;}
for(int i=1;i<=n;i++){int tmp=read();add(i,t,tmp);ans+=tmp;}
m=read();
for(int i=1,k,c;i<=m;i++){
k=read();
c=read();add(s,++cnt,c);ans+=c;
c=read();add(++cnt,t,c);ans+=c;
for(int j=1,x;j<=k;j++){
x=read();
add(cnt-1,x,inf);
add(x,cnt,inf);
}
}
dinic();
cout<<ans-maxflow;
return 0;
}