連結：
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;
}