前置知识：
有源汇上下界最大流
题目简述：
多测，输入多少组，处理多少组，对于每组：
第一行：$n,m$，分别代表 $n$ 天，$m$ 个人。
第二行：$m$ 个数字，$G_1,G_2,…,G_m$。对于每一个 $G_x$ 满足 $G_x\in[0,{10}^5]$，$G_i$ 表示第 $i$ 个人最少拍多少张照片。
接下来 $n$ 天，每一天的第一行两个整数 $C,D$。$D$ 表示每天最多拍 $D$ 张照片。
接下来 $C$ 行，每一行有三个整数 $T,L,R$，其中 $T$ 代表第 $T$ 个人，$L,R$ 分别代表每天最少最多拍的照。
代码思路：
初始化信息，开辟临时源点临时汇点，源点汇点。
读入每个人的最少的照片要求。
和汇点连边，汇点增加流入的“量”，当前节点增加流出的“量”。
- 读入每天最多拍的照片的数量，每天的人的照片的最大最小数量。
每天拍的最大数量和源点连边，边权是 $D_i$ 每天最多拍的照片的数量。
每个人的另一个节点流入的权值是最小的照片数。节点的流出是最小照片数。
另一个节点是 $t_i+n$，就是人的编号加上天数不难发现：$(t_i+1)+(n-1)=t_i+n$，这个人的下一个人在前一天的“另一个节点”和当前人在今天的“另一个节点”用的是同一个节点。
其实，我们在处理网络流的时候，更多时候注意的是边，限制条件也都在边上，所以节点的重复利用问题不大，但是在处理时，还要注意点的数量和边的数量对于时间复杂度的影响。
连边的权值是最大限制和至少的照片数的差。
- 处理所有节点。
如果节点的流入大于要流出，和临时源点连边；相反和临时汇点连边。同时记录所有需要的流量和。
源点和汇点连边。
跑
Dinic。
先用 BFS 找增广路，再用 DFS 处理流量。
如果需求的总量和流量不同，那么无解，相反，有解。
将源点汇点换成真正的源点汇点，跑
Dinic。累计结果，输出。
临时源点汇点的用处在于判断能不能有解，将所有的节点的需求满足。真正的源点汇点处理的是满足每个人的最小需求，同时满足每天的最多的拍摄的照片数量，求出最大流。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int m_a=2147483647;
const int o_o=1e6+10;
int m,n;
int s,t;//源点汇点辅助
int s_1,t_1;//大源点汇点
int s_2,t_2;//临时源点汇点
int b_b;//能否流标记
int a_s;//流量
int s_m;//所有人的需求
int z_s;//答案，最多拍多少张照
//链式前向星
int h_d[o_o],v_v[o_o],n_t[o_o];
int x_p;
int w_t[o_o];//路径最大流量
int l_r[o_o];//反向弧编号
int d_p[o_o];//节点深度
int i_n[o_o],o_t[o_o];//节点流入流出量
int g_i[o_o];//每个人最少拍的照片的数量
queue<int>q_q;
int b_p[o_o];//标记是否在队列中
void a_d(int u,int v,int w,int i_d){//加边
n_t[++x_p]=h_d[u];
h_d[u]=x_p;
v_v[x_p]=v;
w_t[x_p]=w;//累计路径最大流量
l_r[x_p]=i_d;//记录反向弧的编号
}
void b_f(){
//初始化
while(!q_q.empty())q_q.pop();
for(int i=1;i<o_o;i++){
d_p[i]=m_a;//初始化高度
b_p[i]=0;//初始化标记
}
d_p[s]=0;//初始化源点高度
q_q.push(s);//加入源点
while(!q_q.empty()){
int x=q_q.front();
q_q.pop();
b_p[x]=0;//清除标记
for(int i=h_d[x];i;i=n_t[i]){
int v=v_v[i];
if(w_t[i]&&d_p[v]>d_p[x]+1){//有流量并且更新高度
d_p[v]=d_p[x]+1;//更新
if(b_p[v]==0){//没标记过
b_p[v]=1;//标记
q_q.push(v);//入队
}
}
}
}
}
int d_f(int x,int v_l){
if(x==t){//到达汇点
b_b=1;//标记
a_s+=v_l;//累计剩余“流量”
return v_l;
}
int k_k=v_l;//记录剩余“流量”
for(int i=h_d[x];i;i=n_t[i]){
int v=v_v[i];
if(w_t[i]&&d_p[v]==d_p[x]+1){//高度相邻
int n_k=d_f(v,min(k_k,w_t[i]));//记录下一个节点的权值
if(n_k>0){//有路
k_k-=n_k;//更新（有一部分流量流走了）
w_t[i]-=n_k;//更新路径的可留流量限制
w_t[l_r[i]]+=n_k;//反向弧更新
if(k_k==0)break;//没有流量了
}else d_p[v]=0;//没有流量，将点扔掉（没有用了）
}
}
return v_l-k_k;//剩余“流量”
}
int d_i(){
a_s=0;
while(1){
b_f();//找增广路
if(d_p[t]==m_a)break;//无路可走
b_b=1;//标记
while(b_b){
b_b=0;//清除标记
d_f(s,m_a);//开始尝试“流”
//如果成功
}
}
return a_s;//累计流量
}
int main(){
while(~scanf("%d%d",&n,&m)){
//初始化
s_m=x_p=0;
memset(h_d,0,sizeof(h_d));
memset(i_n,0,sizeof(i_n));
memset(o_t,0,sizeof(o_t));
s_1=n+m+1;
t_1=n+m+2;
s_2=n+m+3;
t_2=n+m+4;
s=s_2,t=t_2;
for(int i=1;i<=m;i++){//读入每人至少的照片数量
g_i[i]=r_r();
i_n[t_1]+=g_i[i];//汇点累计权值
o_t[n+i]+=g_i[i];//点流出权值累计
a_d(n+i,t_1,m_a-g_i[i],x_p+2);//连边，记录最大流限制，反向弧的编号
a_d(t_1,n+i,0,x_p);//反向弧
}
for(int i=1;i<=n;i++){//处理每天的基本信息
int c_i=r_r(),d_i=r_r();//每天有多少拍照的人，今天最多拍多少照片
a_d(s_1,i,d_i,x_p+2);//和源点连边，记录最大流限制，反向弧的编号
a_d(i,s_1,0,x_p);//反向弧
for(int j=1;j<=c_i;j++){//处理每个人
int t_i=r_r(),l_i=r_r(),r_i=r_r();//基本信息
t_i++;//将下标从 0 换成 1
i_n[n+t_i]+=l_i;//流入权值累计
o_t[i]+=l_i;//流出价值累计
a_d(i,n+t_i,r_i-l_i,x_p+2);//加边
a_d(n+t_i,i,0,x_p);//反射弧
}
}
for(int i=1;i<=n+m+2;i++){//处理所有节点
if(i_n[i]>o_t[i]){//节点需要有“量”流入
a_d(s,i,i_n[i]-o_t[i],x_p+2);//和源点连边
a_d(i,s,0,x_p);//反向弧
s_m+=i_n[i]-o_t[i];//累计所有节点的需求
}else {//需要有流量流出
a_d(i,t,o_t[i]-i_n[i],x_p+2);//流入汇点
a_d(t,i,0,x_p);//反向弧
}
}
a_d(t_1,s_1,m_a,x_p+2);//源点汇点连边
a_d(s_1,t_1,0,x_p);//反向弧
if(d_i()!=s_m){//不能满足所有的节点需求，无解
puts("-1\n");
continue;
}
z_s=w_t[x_p];//初始化源点汇点边的最大流量
w_t[x_p]=w_t[l_r[x_p]]=0;//清空
//更新源点汇点
s=s_1;
t=t_1;
z_s+=d_i();//计算流量
printf("%d\n\n",z_s);//输出结果
}
return 0;
}
