网络流学习笔记
20231210
不太想写，但是还是写一下吧。
早上被喊起来上课/kk
不愧是 yny，最后 5 分钟不知道讲了多少道题。
最大流
前面没听/kk
Dinic 算法的时间复杂度是是 \(\mathcal O(n^2 m)\)，而在二分图上面可以变成 \(\mathcal O(m \sqrt n)\)
P3163 [CQOI2014] 危桥
Alice 和 Bob 居住在一个由 \(N\) 座岛屿组成的国家，岛屿被编号为 \(0\) 到 \(N-1\)。某些岛屿之间有桥相连，桥上的道路是双向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。
Alice 希望在岛屿 \(a_1\) 和 \(a_2\) 之间往返 \(a_n\) 次（从 \(a1\) 到 \(a2\) 再从 \(a2\) 到 \(a1\) 算一次往返）。同时，Bob 希望在岛屿 \(b_1\) 和 \(b_2\) 之间往返 \(b_n\) 次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问 Alice 和 Bob 能完成他们的愿望吗？
\(4 \leq N\leq 50,\ 0 \leq a_1, a_2, b_1, b_2 \leq N-1,\ 1 \leq a_n, b_n \leq 50\)。
首先没有什么思路——感觉可以跑 \(50\) 次网络流。
考虑直接建图，按照很传统的方式，\(s \to a_1,s \to b_1,a_2 \to t,b_2 \to t\)，
这是容易理解的，而流量就是 \(a_n,b_n\)。
于是跑一次最大流，如果满流，就满足条件？
发现显然是不正确的，对于危桥而言，我们钦定的流量是 \(1\)，但是不排除有可能这个危桥被来回走了两次，
而还有可能 \(a_1 \to b_2,b_1 \to a_2\)，这种也是没有办法排除的。
所以我们现在考虑再构造一种方法，把 \(b_1,b_2\) 交换之后再跑一次网络流，
这样是不是就避免了上面不满足条件的情况？
显然是肯定的，因为路是双向的，如果两者都满流，我们就可以把一些路翻转，
已达到 \(a_1 \to a_2,b_1 \to b_2\) 的目的。
而对于危桥走两次的情况也是显然的，反向之后就不成立了。
于是这样就做完了。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=1e9;
int n,s,t,a1,a2,an,b1,b2,bn,head[N],tot=-1,cur[N],lv[N],ans=0;
struct edge{int v,nxt,w;}e[N<<1];
bool vis[N];
char mp[55][55];
void add(int u,int v,int w){
e[++tot]=(edge){v,head[u],w};head[u]=tot;
e[++tot]=(edge){u,head[v],w};head[v]=tot;
}
bool bfs(){
memset(lv,-1,sizeof(lv));
queue<int> q;
cur[s]=head[s],lv[s]=0,vis[s]=true,q.push(s);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w>0&&lv[v]==-1){
lv[v]=lv[u]+1;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return lv[t]!=-1;
}
int dfs(int u,int flow){
if(u==t) return flow;
int res=flow;
for(int i=cur[u];i!=-1;i=e[i].nxt){
cur[u]=i;int v=e[i].v,w=e[i].w;
if(w&&lv[v]==lv[u]+1){
int c=dfs(v,min(w,res));
e[i].w-=c;
e[i^1].w+=c;
res-=c;
}
}
return flow-res;
}
void dinic(){
ans=0;
while(bfs()) ans+=dfs(s,inf);
}
bool chk(int a1,int a2,int an,int b1,int b2,int bn){
memset(head,-1,sizeof(head));tot=-1;
s=0,t=n+1;
add(s,a1,an);add(s,b1,bn);
add(a2,t,an);add(b2,t,bn);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
if(mp[i][j]=='O') add(i,j,1);
else if(mp[i][j]=='N') add(i,j,inf);
}
dinic();
return (ans==an+bn);
}
void sol(){
scanf("%d%d%d%d%d%d",&a1,&a2,&an,&b1,&b2,&bn);
++a1,++a2,++b1,++b2;
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
if(chk(a1,a2,an,b1,b2,bn)&&chk(a1,a2,an,b2,b1,bn)) puts("Yes");
else puts("No");
}
int main(){
/*2023.12.10 H_W_Y P3163 [CQOI2014] 危桥 网络流*/
while(scanf("%d",&n)!=EOF) sol();
return 0;
}
CF1592F2 Alice and Recoloring 2 - 好题
CF1592F2 Alice and Recoloring 2
给定一个 \(n\) 行 \(m\) 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。
现在你可以矩阵实施以下操作：
使用一块钱，选定一个包含 \((1,1)\) 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。
使用三块钱，选定一个包含 \((n,1)\) 的子矩阵，把矩阵中的元素全部反转。
使用四块钱，选定一个包含 \((1,m)\) 的子矩阵，把矩阵中的元素全部反转。
使用两块钱，选定一个包含 \((n,m)\) 的子矩阵，把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
\(1 \le n,m \le 500\)。
感觉很多操作不知道如何下手。
首先需要发现第 \(2,3\) 种操作是完全没有意义的，
因为可以直接用两次 \(1\) 操作代替，而且代价还会更小。
我们现在想把每次翻转一个区间改成单点修改。
而反转很容易想到 异或 ，那么如果一个点表示的值是一个区间的异或值，只有奇数个点改变时异或值才会变。
于是我们考虑人类智慧构造一下，得到数组 \(a\)，使得
\[a_{i,j} = s_{i,j} \oplus s_{i+1,j} \oplus s_{i,j+1} \oplus s_{i+1,j+1} \]把它画在图上面，我们可以很容易的发现：
- 对于操作 \(1\)，只会改变 \(a_{x,y}\) 的值；
- 对于操作 \(2\)，只会改变形如 \((x,y),(x,m),(n,y),(n,m)\) 这四个值，那么我们把这样的一次操作记作 \(op(x,y)\)。
发现对于操作 \(2\)，只有在 \((x,y),(x,m),(n,y)\) 的值都是 \(1\) 的时候我们才会用，
反之直接用操作 \(1\)，是一定不劣的。
而如果两次连续操作 \(op(x,y1),op(x,y2)\) 是不优的，因为我们可以直接用操作 \(1\) 完成。
所以对于每一个 \(x,y\)，它最多只会被涉及一次操作，
那么这时就想到了矩形的常见建图方法，我们把每一个 \(x\) 连到 \(s\)，\(y\) 连到 \(t\)，
于是跑一次二分图最大匹配即可，最后的答案也是好处理的。
最小割
由最小割定理可以得到最小割等于最大流，
感觉感性理解还是很好理解的。
P4313 文理分科
典题。
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）
小 P 所在的班级要进行文理分科。他的班级可以用一个 \(n\times m\) 的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：
如果第 \(i\) 行第 \(j\) 列的同学选择了文科，则他将获得 \(art_{i,j}\) 的满意值，如果选择理科，将得到 \(science_{i,j}\) 的满意值。
如果第 \(i\) 行第 \(j\) 列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加 \(same\_art_{i,j}\) 的满意值。
如果第 \(i\) 行第 \(j\) 列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加 \(same \_ science_{i,j}\) 的满意值。
小 P 想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。
\(n,m\leq 100\)，读入数据均 \(\leq 500\)。
同样是类似于分成两个集合，求最小割。
而最小割如何构造，首先对于单个点的贡献是好构造的，
而对于每一个多个点同时选择得到的权值也是好计算的，
直接新建一个节点向这些点连边，于是再从 \(s,t\) 连一下边于是就可以跑最小割了。
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5,inf=1e9;
int n,m,cnt=0,head[N],tot=-1,cur[N],lv[N],s,t,ans=0,sum=0;
struct edge{int v,nxt,w;}e[N<<1];
bool vis[N];
void add(int u,int v,int w){
e[++tot]=(edge){v,head[u],w};head[u]=tot;
e[++tot]=(edge){u,head[v],0};head[v]=tot;
}
bool bfs(){
memset(lv,-1,sizeof(lv));
queue<int> q;
lv[s]=0;q.push(s);
cur[s]=head[s];vis[s]=true;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w>0&&lv[v]==-1){
lv[v]=lv[u]+1;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return lv[t]!=-1;
}
int dfs(int u,int flow){
if(u==t) return flow;
int res=flow;
for(int i=cur[u];i!=-1;i=e[i].nxt){
cur[u]=i;
int v=e[i].v,w=e[i].w;
if(w&&lv[v]==lv[u]+1){
int c=dfs(v,min(w,res));
res-=c;
e[i].w-=c;
e[i^1].w+=c;
}
}
return flow-res;
}
void dinic(){
ans=0;
while(bfs()) ans+=dfs(s,inf);
}
int id(int i,int j){return (i-1)*m+j;}
const int fx[5]={0,0,0,-1,1},fy[5]={0,1,-1,0,0};
void ins1(int i,int j,int v){
++cnt;
add(s,cnt,v);
for(int k=0;k<5;k++){
int x=i+fx[k],y=j+fy[k];
if(x>0&&y>0&&x<=n&&y<=m) add(cnt,id(x,y),inf);
}
}
void ins2(int i,int j,int v){
++cnt;
add(cnt,t,v);
for(int k=0;k<5;k++){
int x=i+fx[k],y=j+fy[k];
if(x>0&&y>0&&x<=n&&y<=m) add(id(x,y),cnt,inf);
}
}
int main(){
/*2023.12.10 H_W_Y P4313 文理分科 最小割*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
memset(head,-1,sizeof(head));
s=0;cnt=n*m+1;t=cnt;
for(int i=1;i<=n;i++)
for(int j=1,x;j<=m;j++)
cin>>x,add(s,id(i,j),x),sum+=x;
for(int i=1;i<=n;i++)
for(int j=1,x;j<=m;j++)
cin>>x,add(id(i,j),t,x),sum+=x;
for(int i=1;i<=n;i++)
for(int j=1,x;j<=m;j++)
cin>>x,ins1(i,j,x),sum+=x;
for(int i=1;i<=n;i++)
for(int j=1,x;j<=m;j++)
cin>>x,ins2(i,j,x),sum+=x;
dinic();
cout<<(sum-ans)<<'\n';
return 0;
}
P3227 [HNOI2013] 切糕
经过千辛万苦小 A 得到了一块切糕，切糕的形状是长方体，小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑，小 A 希望切面能尽量光滑且和谐。于是她找到你，希望你能帮她找出最好的切割方案。
出于简便考虑，我们将切糕视作一个长 \(P\)、宽 \(Q\)、高 \(R\) 的长方体点阵。我们将位于第 \(z\) 层中第 \(x\) 行、第 \(y\) 列上的点称 \((x,y,z)\)，它有一个非负的不和谐值 \(v(x,y,z)\)。一个合法的切面满足以下两个条件：
与每个纵轴（一共有 \(P\times Q\) 个纵轴）有且仅有一个交点。即切面是一个函数 \(f(x,y)\)，对于所有 \((x,y)(x\in [1,P],y\in[1,Q])\)，我们需指定一个切割点 \(f(x,y)\)，且 \(1\le f(x,y)\le R\)。
切面需要满足一定的光滑性要求，即相邻纵轴上的切割点不能相距太远。对于所有的 \(1\le x,x'\le P\) 和 \(1\le y,y'\le Q\)，若 \(|x-x'|+|y-y'|=1\)，则 \(|f(x,y)-f(x',y')| \le D\)，其中 \(D\) 是给定的一个非负整数。
可能有许多切面 \(f\) 满足上面的条件，小 A 希望找出总的切割点上的不和谐值最小的那个。
对于 \(100\%\) 的数据，\(1 \leq P,Q,R\leq 40,0\le D\le R\)，且给出的所有的不和谐值不超过 \(1000\)。
题目就感觉比较抽象。/kk
考虑我们直接建图，也就是将每一层穿起来，
但是发现这样很难满足 \(d\) 的性质，
而 \(d\) 的性质满足的要素其实就是在答案为选两个差为 \(d\) 以上的点的时候，
这个答案会被覆盖掉，也就是根本不存在了。
那么我们最开始都是从 \((i,j,k) \to (i,j,k+1),w=a[i][j][k]\) 的边，
而为了满足 \(d\) 的条件，我们再建 \((i,j,k) \to (x,y,k-d),w=\inf\) 的边，其中 \((x,y)\) 与 \((i,j)\) 相邻，
这样建图之后我们发现不合法的条件一定不会成为答案，所以直接跑最小割即可。
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int N=55,fx[4]={-1,1,0,0},fy[4]={0,0,-1,1},P=1e5+5,M=5e6+5,inf=1e9;
int n,m,h,d,a[N][N][N],head[P],tot=-1,lv[P],cur[P],s,t;
struct edge{int v,nxt,w;}e[M];
bool vis[P];
void add(int u,int v,int w){
e[++tot]=(edge){v,head[u],w};head[u]=tot;
e[++tot]=(edge){u,head[v],0};head[v]=tot;
}
bool bfs(){
memset(lv,-1,sizeof(lv));
queue<int> q;q.push(s);
vis[s]=true;cur[s]=head[s];lv[s]=0;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&lv[v]==-1){
lv[v]=lv[u]+1;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return lv[t]!=-1;
}
int dfs(int u,int flow){
if(u==t) return flow;
int res=flow;
for(int i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;cur[u]=i;
if(w&&lv[v]==lv[u]+1){
int c=dfs(v,min(w,res));
res-=c;e[i].w-=c,e[i^1].w+=c;
}
if(!res) break;
}
return flow-res;
}
int dinic(){
int ans=0;
while(bfs()) ans+=dfs(s,inf);
return ans;
}
int id(int i,int j,int k){return (k-1)*n*m+(i-1)*m+j;}
int main(){
/*2023.12.11 H_W_Y P3227 [HNOI2013] 切糕 最小割最大流*/
n=read();m=read();h=read();d=read();
memset(head,-1,sizeof(head));tot=-1;
s=0,t=n*m*h+1;
for(int k=1;k<=h;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
a[k][i][j]=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
add(s,id(i,j,1),inf);
for(int k=1;k<h;++k) add(id(i,j,k),id(i,j,k+1),a[k][i][j]);
add(id(i,j,h),t,a[h][i][j]);
for(int p=0;p<4;++p){
int x=i+fx[p],y=j+fy[p];
if(x>0&&y>0&&x<=n&&y<=m)
for(int k=d+1;k<=h;++k) add(id(i,j,k),id(x,y,k-d),inf);
}
}
printf("%d\n",dinic());
return 0;
}
P4897 【模板】最小割树（Gomory-Hu Tree）
P4897 【模板】最小割树（Gomory-Hu Tree）
求最小割树。
这里只是想放一个板子。/kk
#include <bits/stdc++.h>
using namespace std;
const int N=505,M=1e5+5,inf=1e9;
int n,m,Q,head[N],tot=-1,cur[N],lv[N],ans[N][N],s,t,a[N],tmp1[N],tmp2[N];
struct edge{int v,nxt,w;}e[M<<1];
bool vis[N];
void add(int u,int v,int w){
e[++tot]=(edge){v,head[u],w};head[u]=tot;
e[++tot]=(edge){u,head[v],0};head[v]=tot;
}
bool bfs(){
memset(lv,-1,sizeof(lv));
queue<int> q;q.push(s);
vis[s]=true;cur[s]=head[s],lv[s]=0;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&lv[v]==-1){
lv[v]=lv[u]+1;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return lv[t]!=-1;
}
int dfs(int u,int flow){
if(u==t) return flow;
int res=flow;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&lv[v]==lv[u]+1){
int c=dfs(v,min(res,w));
res-=c;e[i].w-=c;e[i^1].w+=c;
}
if(!res) break;
}
return flow-res;
}
void init(){
for(int i=0;i<tot;i+=2)
e[i].w+=e[i^1].w,e[i^1].w=0;
}
int dinic(){
int res=0;init();
while(bfs()) res+=dfs(s,inf);
return res;
}
void wrk(int l,int r){
if(l==r) return ;
s=a[l],t=a[l+1];
int res=dinic(),S=a[l],T=a[l+1],cnt1=0,cnt2=0;
ans[S][T]=ans[T][S]=res;
for(int i=l;i<=r;i++){
if(lv[a[i]]!=-1) tmp1[++cnt1]=a[i];
else tmp2[++cnt2]=a[i];
}
for(int i=1;i<=cnt1;i++) a[l+i-1]=tmp1[i];
for(int i=1;i<=cnt2;i++) a[l+cnt1+i-1]=tmp2[i];
wrk(l,l+cnt1-1);wrk(l+cnt1,r);
for(int i=1;i<=cnt1;i++)
for(int j=1;j<=cnt2;j++){
int x=a[l+i-1],y=a[l+cnt1+j-1];
ans[x][y]=ans[y][x]=min(min(ans[S][x],ans[y][T]),ans[S][T]);
}
}
int main(){
/*2023.12.11 H_W_Y P4897 【模板】最小割树（Gomory-Hu Tree） 最小割*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
memset(ans,0x3f,sizeof(ans));
memset(head,-1,sizeof(head));tot=-1;
for(int i=0;i<=n;i++) a[i]=i;
for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,add(u,v,w),add(v,u,w);
wrk(0,n);
cin>>Q;
while(Q--){
int u,v;cin>>u>>v;
cout<<ans[u][v]<<'\n';
}
return 0;
}
P4123 [CQOI2016] 不同的最小割 - 最小割树
一张 \(n\) 个点 \(m\) 条边的图，每一对点的最小割中，有多少个互不相同。
\(1 \le n \le 1000,1 \le m \le 10000\)。
首先引入一个东西叫做最小割树，顾名思义，就是一棵由最小割建出来的树。
最小割树的每一条边就代表着这两边两个集合的最小割，这是好理解的，
于是任意两个点的最小割就是树上的最小边的长度。
而这道题就是问树边有多少个不同的点，用 set 维护一下即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5,M=5e4+5,inf=1e9;
int n,m,head[N],tot=-1,cur[N],lv[N],s,t,tmp1[N],tmp2[N],a[N];
struct edge{int v,nxt,w;}e[M];
bool vis[N];
void add(int u,int v,int w){
e[++tot]=(edge){v,head[u],w};head[u]=tot;
e[++tot]=(edge){u,head[v],0};head[v]=tot;
}
bool bfs(){
memset(lv,-1,sizeof(lv));
queue<int> q;q.push(s);
cur[s]=head[s],lv[s]=0,vis[s]=true;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&lv[v]==-1){
lv[v]=lv[u]+1;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return lv[t]!=-1;
}
int dfs(int u,int flow){
if(u==t) return flow;
int res=flow;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&lv[v]==lv[u]+1){
int c=dfs(v,min(res,w));
res-=c;e[i].w-=c;e[i^1].w+=c;
}
if(!res) break;
}
return flow-res;
}
void init(){
for(int i=0;i<tot;i+=2) e[i].w+=e[i^1].w,e[i^1].w=0;
}
int dinic(){
int res=0;init();
while(bfs()) res+=dfs(s,inf);
return res;
}
set<int> st;
void wrk(int l,int r){
if(l==r) return;
s=a[l];t=a[l+1];
int res=dinic(),cnt1=0,cnt2=0;
for(int i=l;i<=r;i++)
if(lv[a[i]]!=-1) tmp1[++cnt1]=a[i];
else tmp2[++cnt2]=a[i];
st.insert(res);
for(int i=1;i<=cnt1;i++) a[l+i-1]=tmp1[i];
for(int i=1;i<=cnt2;i++) a[l+cnt1+i-1]=tmp2[i];
wrk(l,l+cnt1-1);wrk(l+cnt1,r);
}
int main(){
/*2023.12.11 H_W_Y P4123 [CQOI2016] 不同的最小割 最小割树*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;memset(head,-1,sizeof(head));tot=-1;
for(int i=1;i<=n;i++) a[i]=i;
for(int i=1,u,v,w;i<=m;i++) cin>>u>>v>>w,add(u,v,w),add(v,u,w);
wrk(1,n);cout<<st.size()<<'\n';
return 0;
}
然而 loj 需要把 \(a\) rand 一下才可以过。
最大权闭合子图
给定一个有向图，点有点权。
如果一个点 \(u\) 被选了，所有 \(u\) 的出边指向的点 \(v\) 也必须选。
求最大收益。（点权可以为负数）
利用最小割来解决。先假设所有正点权都选。
正点权连到 \(st\)，表示放弃这个点，负点权连到 \(ed\)，表示选择这个点。
原图中所有 \((u, v)\) 连接一条 \((u, v, \inf)\) 的边。
感觉还比较好理解
P4177 [CEOI2008] order
有 \(m\) 个工作，\(m\) 种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序， 每道工序需要某种机器来完成，你可以通过购买或租用机器来完成。
租用的机器只能用一次，可以多次租用。现在给出这些参数，求最大利润。
\(1 \le n \le 1200, 1 \le m \le 1200\)。
同样是最大权最小子图，只不过多了一个租用的操作。
租用也是比较好处理的。
我们直接把中间的边的容量 \(inf\) 改成租用的费用即可。
网络流一定要剪枝！！！
#include <bits/stdc++.h>
using namespace std;
const int N=3e6+5,inf=0x3f3f3f3f;
int n,m,head[N],st,ed,tot=-1,sum=0,cur[N],lv[N],l,r,q[N];
struct edge{
int v,nxt,val;
}e[N<<2];
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
void add(int u,int v,int w){
e[++tot]=(edge){v,head[u],w};
head[u]=tot;
e[++tot]=(edge){u,head[v],0};
head[v]=tot;
}
bool bfs(){
for(int i=0;i<=ed;i++) lv[i]=-1;
lv[st]=1;
cur[st]=head[st];
q[l=1]=st;r=1;
while(l<=r){
int u=q[l++];
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,val=e[i].val;
if(val>0&&lv[v]==-1){
lv[v]=lv[u]+1;
cur[v]=head[v];
q[++r]=v;
if(v==ed) return true;
}
}
}
return lv[ed]!=-1;
}
int dfs(int u,int flow){
if(u==ed) return flow;
int res=flow;
for(int i=cur[u];i!=-1;i=e[i].nxt){
cur[u]=i;
int v=e[i].v,val=e[i].val;
if(val>0&&lv[v]==lv[u]+1){
int c=dfs(v,min(res,val));
if(!c) lv[v]=-1;
res-=c;
e[i].val-=c;
e[i^1].val+=c;
}
if(res==0) break;//网络流剪枝很有必要！！！
}
if(res!=0) lv[u]=-1;
return flow-res;
}
int dinic(){
int res=0;
while(bfs()) res+=dfs(st,inf);
return res;
}
int main(){
/*2023.8.23 H_W_Y P4177 [CEOI2008] order 网络流+最大权闭合子图*/
memset(head,-1,sizeof(head));tot=-1;
n=read();m=read();
st=0,ed=n+m+1;
for(int i=1,x,t;i<=n;i++){
x=read();add(st,i,x);sum+=x;
t=read();
for(int j=1,a,b;j<=t;j++){
a=read();b=read();
add(i,a+n,b);
}
}
for(int i=1,x;i<=m;i++){x=read();add(i+n,ed,x);}
printf("%d\n",sum-dinic());
return 0;
}
上下界网络流
以前不会，听了还是不会。
学习了一会儿，感觉也没有那么难。
首先无源汇上下界可行流是简单的，
我们就假设都跑满了下界建图之后跑网络流。
转到有源汇上面，
就是先跑一次无源汇使得流量平衡之后再在残图上面跑一次网络流即可。
感觉挺好懂的。
CF1416F Showing Off
对于大小为 \(n\cdot m\) 的矩阵 \(A\) 和 \(B\)，其中 \(A\) 的每个元素为一个权值 \(w(i,j)\)，\(B\) 的每个元素为一个方向
L/R/D/U初始你在 \((i,j)\)，若 \(B_{i,j}=L\)，你可以走到 \((i,j-1)\) 处，依次类推。
定义 \(S_{i,j}\) 表示从 \((i,j)\) 出发能够到达的点的 \(A_{i,j}\) 的和。
给定矩阵 \(S\)，构造 \(A\) 和 \(B\) 使得其生成的矩阵为 \(S\)
\(A\) 的每个元素均为正整数。
\(1\le n\cdot m\le 10^5,S_{i,j}\in [2,10^9]\)
很妙的一道题啊。
首先观察样例可以得到，一条路径的端点一定是一个环，
也就是说构成了一个基环树森林。
而在这个环上面的每一个点 \(s\) 值是一样的。
现在来考虑如何构造，
对于一个点 \((i,j)\)，如果它四周没有比它小的点，那么它一定是在环上面的，
反之，它有可能在环上有可能不在环上。
而由于整个图是一个四联通性的，
所以每一个环一定是一个偶环，于是我们可以直接把偶环拆成很多个二元环，
而这种情况和之前是类似的，构造也是好构造的。
对于非环的点，我们可以钦定它的下一个点是什么，
于是直接连一条边即可，而点权则是两点之差。
对于环，我们就只希望构造出这些合法的二元组使得两两不交，
而这个就启发我们用黑白染色去解决。
于是这个问题就变成了在一张图上面构造一些合法的不交二元环，
而允许存在一些点即可选择成为环上的点，又可以不成为环上的点，
这是用上下界最大流完成的（对于非环上的点我们连到旁边的点的流量范围是 \([0,1]\)）。
无解的情况就是没有可行流。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,inf=1e9;
int n,m,Q,head[N],tot=-1,cur[N],lv[N],s,t,S,T,dt[N],cnt,a[N],b[N];
char c[N];
bool vis[N],fl[N];
struct edge{int v,nxt,w;}e[N<<4];
const int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};
const char pos[4]={'R','L','D','U'},rev[4]={'L','R','U','D'};
void add(int u,int v,int w){
e[++tot]=(edge){v,head[u],w};head[u]=tot;
e[++tot]=(edge){u,head[v],0};head[v]=tot;
}
void addlr(int u,int v,int l,int r){
add(u,v,r-l);
dt[u]-=l,dt[v]+=l;
}
bool bfs(){
memset(lv,-1,sizeof(lv));
queue<int> q;q.push(s);
lv[s]=0;cur[s]=head[s],vis[s]=true;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&lv[v]==-1){
lv[v]=lv[u]+1;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return lv[t]!=-1;
}
int dfs(int u,int flow){
if(u==t) return flow;
int res=flow;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(w&&lv[v]==lv[u]+1){
int nw=dfs(v,min(w,res));
res-=nw;e[i].w-=nw;e[i^1].w+=nw;
}
if(!res) break;
}
return flow-res;
}
int dinic(){
int res=0;
while(bfs()) res+=dfs(s,inf);
return res;
}
int id(int i,int j){return (i-1)*m+j;}
bool chk(int i,int j){return (i>0&&j>0&&i<=n&&j<=m);}
void init(){
for(int i=1;i<=n*m;i++) vis[i]=fl[i]=false,lv[i]=b[i]=0;
for(int i=s;i<=t;i++) head[i]=-1,dt[i]=0;
cnt=0,tot=-1;
}
void sol(){
cin>>n>>m;
s=0;t=n*m+3;S=n*m+1,T=n*m+2;
for(int i=1;i<=n*m;i++) cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
bool flg=true;
for(int k=0;k<4;k++){
int x=fx[k]+i,y=fy[k]+j;
if(chk(x,y)&&a[id(x,y)]<a[id(i,j)]) flg=false;
}
fl[id(i,j)]=flg;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if((i+j)&1){
addlr(S,id(i,j),fl[id(i,j)],1);
for(int k=0;k<4;k++){
int x=fx[k]+i,y=fy[k]+j;
if(chk(x,y)&&a[id(x,y)]==a[id(i,j)]) addlr(id(i,j),id(x,y),0,1);
}
}else addlr(id(i,j),T,fl[id(i,j)],1);
}
addlr(T,S,0,inf);
for(int i=1;i<=n*m+2;i++){
if(dt[i]>0) add(s,i,dt[i]),cnt+=dt[i];
else add(i,t,-dt[i]);
}
if(dinic()!=cnt){cout<<"NO\n";return;}
else cout<<"YES\n";
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if((i+j)&1){
for(int k=head[id(i,j)];k!=-1;k=e[k].nxt){
int v=e[k].v;
if(v==S||v==s||e[k^1].w==0) continue;
b[id(i,j)]=1,b[v]=a[v]-1;
for(int l=0;l<4;l++){
int x=fx[l]+i,y=fy[l]+j;
if(chk(x,y)&&id(x,y)==v) c[id(i,j)]=pos[l],c[v]=rev[l];
}
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(b[id(i,j)]) continue;
for(int k=0;k<4;k++){
int x=i+fx[k],y=fy[k]+j;
if(chk(x,y)&&a[id(x,y)]<a[id(i,j)]){
b[id(i,j)]=a[id(i,j)]-a[id(x,y)];
c[id(i,j)]=pos[k];
}
}
}
for(int i=1;i<=n;cout<<'\n',i++) for(int j=1;j<=m;j++) cout<<b[id(i,j)]<<' ';
for(int i=1;i<=n;cout<<'\n',i++) for(int j=1;j<=m;j++) cout<<c[id(i,j)]<<' ';
}
int main(){
/*2023.12.12 H_W_Y CF1416 Showing Off 上下界可行流*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
memset(head,-1,sizeof(head));tot=-1;
cin>>Q;
while(Q--) sol(),init();
return 0;
}
最小费用最大流
嗯。
P2053 [SCOI2007] 修车
同一时刻有 \(N\) 位车主带着他们的爱车来到了汽车维修中心。
维修中心共有 \(M\) 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。
现在需要安排这 \(M\) 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
\(2\le M\le 9\)，\(1\le N\le 60\)，\(1\le T\le 10^3\)。
感觉就很想网络流，但是又很难去排顺序。
首先构成一个二分图，左边是车，右边是人，
那么如何做到车辆按照顺序呢？
我们考虑 拆点，把每一个工人拆成 \(n\) 个点，每一个点表示他修他的倒数第 \(i\) 辆车所用的时间。
于是费用是好计算的，直接 \(i \times t_j\) 即可，这个推一推就可以知道。
直接跑一次费用流就可以了。
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5,inf=1e9;
int n,m,head[N],tot=-1,cur[N],dis[N],s,t,ans=0,ansc=0;
struct edge{int v,nxt,w,c;}e[N*N];
bool vis[N];
void add(int u,int v,int w,int c){
e[++tot]=(edge){v,head[u],w,c};head[u]=tot;
e[++tot]=(edge){u,head[v],0,-c};head[v]=tot;
}
bool spfa(){
for(int i=0;i<=t;i++) dis[i]=inf,vis[i]=false;
queue<int> q;
q.push(s);vis[s]=true;
cur[s]=head[s];dis[s]=0;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w,c=e[i].c;
if(w&&dis[v]>dis[u]+c){
dis[v]=dis[u]+c;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int flow){
vis[u]=true;
if(u==t) return flow;
int res=flow;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w,c=e[i].c;
if(w&&!vis[v]&&dis[v]==dis[u]+c){
int nw=dfs(v,min(res,w));
res-=nw;e[i].w-=nw;e[i^1].w+=nw;
}
if(!res) break;
}
return flow-res;
}
void dinic(){
while(spfa()){
int nw=dfs(s,inf);
ans+=nw,ansc+=dis[t]*nw;
}
}
int main(){
/*2023.12.12 H_W_Y P2053 [SCOI2007] 修车 最小费用最大流*/
scanf("%d%d",&m,&n);
memset(head,-1,sizeof(head));tot=-1;
for(int i=1;i<=n;i++)
for(int j=1,x;j<=m;j++){
scanf("%d",&x);
for(int k=1;k<=n;k++) add(i,j*n+k,1,x*k);
}
s=0,t=n*(m+1)+1;
for(int i=1;i<=n;i++) add(s,i,1,0);
for(int i=1;i<=n*m;i++) add(i+n,t,1,0);
dinic();
printf("%.2lf\n",1.0*ansc/n);
return 0;
}
P3705 [SDOI2017] 新生舞会
学校组织了一次新生舞会，Cathy 作为经验丰富的老学姐，负责为同学们安排舞伴。
有 \(n\) 个男生和 \(n\) 个女生参加舞会，一个男生和一个女生一起跳舞，互为舞伴。
Cathy 收集了这些同学之间的关系，比如两个人之前认识没，计算得出 \(a_{i,j}\)。
Cathy 还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 \(b_{i,j}\)，表示第 \(i\) 个男生和第 \(j\) 个女生一起跳舞时的不协调程度。
当然，还需要考虑很多其他问题。
Cathy 想先用一个程序通过 \(a_{i,j}\) 和 \(b_{i,j}\) 求出一种方案，再手动对方案进行微调。
Cathy 找到你，希望你帮她写那个程序。
一个方案中有 n 对舞伴，假设没对舞伴的喜悦程度分别是 \(a'_1,a'_2,...,a'_n\)，假设每对舞伴的不协调程度分别是 \(b'_1,b'_2,...,b'_n\)。令
\(C=\frac {a'_1+a'_2+...+a'_n}{b'_1+b'_2+...+b'_n}\)
Cathy 希望 \(C\) 值最大。
\(1\le n\le 100,1\le a_{i,j},b_{i,j}\le10^4\)。
发现直接求 \(C\) 是非常困难的。
我们做一些分数规划，
发现 \(\sum a_i - \sum{b_i} \times C = 0\)，
那么容易想到去二分 \(C\)，于是我们就是要求 \(a_i-b_i \times C\) 的最大值，
这个可以直接用网络流完成了，
具体就是分成二分图，每一条边的费用就是 \(a_i - b_i \times C\)，我们只需要求出最大费用最大流即可。
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-8
#define db double
const int N=1e5+5,M=105,inf=1e9;
int n,head[N],tot=-1,cur[N],s,t,a[105][105],b[105][105];
bool vis[N];
db ansc=0,dis[N];
struct edge{int v,nxt,w;db c;}e[N<<1];
void add(int u,int v,int w,db c){
e[++tot]=(edge){v,head[u],w,c};head[u]=tot;
e[++tot]=(edge){u,head[v],0,-c};head[v]=tot;
}
bool spfa(){
for(int i=s;i<=t;i++) dis[i]=-1.0*inf,vis[i]=false;
queue<int> q;q.push(s);
cur[s]=head[s],vis[s]=true,dis[s]=0;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;db c=e[i].c;
while(w&&dis[v]<dis[u]+c){
dis[v]=dis[u]+c;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return dis[t]!=-1.0*inf;
}
int dfs(int u,int flow){
vis[u]=true;
if(u==t) return flow;
int res=flow;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;db c=e[i].c;
if(!vis[v]&&w&&dis[v]==dis[u]+c){
int nw=dfs(v,min(res,w));
if(nw<=0) continue;
res-=nw;e[i].w-=nw;e[i^1].w+=nw;
}
if(!res) break;
}
return flow-res;
}
void dinic(){
ansc=0;
while(spfa()){
vis[t]=true;
while(vis[t]){
for(int i=0;i<=t;i++) vis[i]=false;
db nw=dfs(s,inf);ansc+=1.0*nw*dis[t];
}
}
}
bool chk(db x){
s=0,t=2*n+1;
for(int i=0;i<=t;i++) head[i]=-1,vis[i]=false;tot=-1;
for(int i=1;i<=n;i++) add(s,i,1,0),add(i+n,t,1,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
add(i,j+n,1,1.0*a[i][j]-1.0*x*b[i][j]);
dinic();
return ansc>=0;
}
void sol(){
db r=10005,l=0,ans=0;
while(r-l>eps){
db mid=(l+r)/2.0;
if(chk(mid)) ans=mid,l=mid+eps;
else r=mid-eps;
}
printf("%.6lf\n",ans);
}
int main(){
/*2023.12.12 H_W_Y P3705 [SDOI2017] 新生舞会 最小费用最大流*/
scanf("%d",&n);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&b[i][j]);
sol();return 0;
}
注意 eps 一定要取小一点。
P3980 [NOI2008] 志愿者招募
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要 \(n\) 天才能完成，其中第 \(i\) 天至少需要 \(a_i\) 个人。布布通过了解得知，一共有 \(m\) 类志愿者可以招募。其中第 \(i\) 类可以从第 \(s_i\) 天工作到第 \(t_i\) 天，招募费用是每人 \(c_i\) 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
\(1\leq n\leq 1000\)，\(1\leq m\leq 10000\)，题目中其他所涉及的数据均不超过 \(2^{31}-1\)。
发现图中的每一类志愿者是只要你选了它就会给你干 \(s \sim t\) 天，这并不是好处理的。
既然上一天的志愿者要延续到下一天，而这道题读起来很想最小费用最大流，我把人数变成流量。
于是我们考虑从 \(i \to i+1\) 建立一条流量为 \(-a[i]\) 的边，比较好理解。
那么如何去满足人数的限制条件呢？
发现每一类志愿者干都会一直干到 \(t\) 天，
也就是说在 \(s\) 天开始这些志愿者人数时不变的，直到 \(t+1\) 天他们就不干了，
于是我们可以建立一条 \(s \to t+1\) 的边，流量为 \(\inf\)，那么这样就表示到 \(t+1\) 那天往下流的时候，这一天对下一天的贡献会减小。
而费用就是我们题目中的 \(c_i\) 即可，最后我们希望总的流量为 \(0\)。
但是考虑网络流的流量不能是负数，所以直接把 \(-a[i]\) 变成 \(\inf - a[i]\)，这样流量最终就是 \(\inf\) 即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5,inf=1e9;
int n,m,head[N],tot=-1,dis[N],cur[N],s,t;
bool vis[N];
struct edge{int v,nxt,w,c;}e[N*N];
void add(int u,int v,int w,int c){
e[++tot]=(edge){v,head[u],w,c};head[u]=tot;
e[++tot]=(edge){u,head[v],0,-c};head[v]=tot;
}
bool spfa(){
for(int i=0;i<=t;i++) dis[i]=inf,vis[i]=false;
queue<int> q;q.push(s);
cur[s]=head[s],vis[s]=true,dis[s]=0;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w,c=e[i].c;
if(w&&dis[v]>dis[u]+c){
dis[v]=dis[u]+c;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int flow){
vis[u]=true;
if(u==t) return flow;
int res=flow;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w,c=e[i].c;
if(!vis[v]&&w&&dis[v]==dis[u]+c){
int nw=dfs(v,min(w,res));
res-=nw,e[i].w-=nw,e[i^1].w+=nw;
}
if(!res) break;
}
return flow-res;
}
int dinic(){
int res=0;
while(spfa()){
vis[t]=true;
while(vis[t]){
for(int i=s;i<=t;i++) vis[i]=false;
int nw=dfs(s,inf);res+=nw*dis[t];
}
}
return res;
}
int main(){
/*2023.12.12 H_W_Y P3980 [NOI2008] 志愿者招募 最小费用最大流*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;memset(head,-1,sizeof(head));tot=-1;
s=0,t=n+2;
for(int i=1,x;i<=n;i++) cin>>x,add(i,i+1,inf-x,0);
for(int i=1,si,ti,x;i<=m;i++) cin>>si>>ti>>x,add(si,ti+1,inf,x);
add(s,1,inf,0);add(n+1,t,inf,0);
cout<<dinic()<<'\n';
return 0;
}
[AGC031E] Snuke the Phantom Thief
[AGC031E] Snuke the Phantom Thief
在二维平面上，有 \(n\) 颗珠宝，第\(i\)颗珠宝在 \((x_i,y_i)\) 的位置，价值为 \(v_i\)。
现在有一个盗贼想要偷这些珠宝。
现在给出 \(m\) 个限制约束偷的珠宝，约束有以下四种：
- 横坐标小于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 横坐标大于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 纵坐标小于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 纵坐标大于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
这四个限制输入的时候分别用LRDU四个字母来区分。
现在问你在满足这些约束的条件下，盗贼偷的珠宝的最大价值和是多少。
\(1 \le n \le 80, 1\le m \le 320\)。
挺有意思的一道题。
首先感觉可以去网络流，但是最多的限制就非常难搞，所以我们考虑把它变成最小。
于是不难想到去枚举答案，这样被选的每一颗宝石就有了要求，即 \([lx,rx],[ly,ry]\)。
这是很好求出来的，于是直接建图跑最大费用最大流即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5,inf=1e9,M=105;
const ll INF=1e18;
int n,m,head[N],s,t,fl,tot=-1,cur[N],Lx[M],Ly[M],Rx[M],Ry[M];
ll dis[N],ans,sum=0;
bool vis[N];
struct pnt{int x,y;ll v;}a[M];
struct qry{char ch;int x,y;}p[505];
struct edge{int v,nxt,w;ll c;}e[N<<1];
void add(int u,int v,int w,ll c){
e[++tot]=(edge){v,head[u],w,c};head[u]=tot;
e[++tot]=(edge){u,head[v],0,-c};head[v]=tot;
}
bool spfa(){
for(int i=s;i<=t;i++) dis[i]=-INF,vis[i]=false;
queue<int> q;q.push(s);
dis[s]=0,cur[s]=head[s],vis[s]=true;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;ll c=e[i].c;
if(w&&dis[v]<dis[u]+c){
dis[v]=dis[u]+c;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return dis[t]!=-INF;
}
int dfs(int u,int flow){
vis[u]=true;
if(u==t) return flow;
int res=flow;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w;ll c=e[i].c;
if(w&&!vis[v]&&dis[v]==dis[u]+c){
int nw=dfs(v,min(res,w));
res-=nw;e[i].w-=nw,e[i^1].w+=nw;
}
if(!res) break;
}
return flow-res;
}
void dinic(){
fl=0,ans=0;
while(spfa()){
vis[t]=true;
while(vis[t]){
for(int i=s;i<=t;i++) vis[i]=false;
int nw=dfs(s,inf);fl+=nw,ans+=1ll*nw*dis[t];
}
}
}
int main(){
/*2023.12.12 H_W_Y [AGC031E] Snuke the Phantom Thief 最大费用最大流*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].v;
cin>>m;
for(int i=1;i<=m;i++) cin>>p[i].ch>>p[i].x>>p[i].y;
for(int k=1;k<=n;k++){
s=0,t=2*k+2*n+1;
for(int i=s;i<=t;i++) head[i]=-1,vis[i]=false;tot=-1;
for(int i=1;i<=k;i++) add(s,i,1,0);
for(int i=2*n+k+1;i<t;i++) add(i,t,1,0);
for(int i=k+1;i<=k+n;i++) add(i,i+n,1,a[i-k].v);
for(int i=1;i<=k;i++) Lx[i]=Ly[i]=0,Rx[i]=Ry[i]=inf;
for(int i=1;i<=m;i++){
if(p[i].ch=='L') for(int j=p[i].y+1;j<=k;j++) Lx[j]=max(Lx[j],p[i].x+1);
if(p[i].ch=='R') for(int j=1;j<=k-p[i].y;j++) Rx[j]=min(Rx[j],p[i].x-1);
if(p[i].ch=='U') for(int j=1;j<=k-p[i].y;j++) Ry[j]=min(Ry[j],p[i].x-1);
if(p[i].ch=='D') for(int j=p[i].y+1;j<=k;j++) Ly[j]=max(Ly[j],p[i].x+1);
}
for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
if(Lx[i]<=a[j].x&&a[j].x<=Rx[i]) add(i,j+k,1,0);
for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
if(Ly[i]<=a[j].y&&a[j].y<=Ry[i]) add(j+k+n,i+2*n+k,1,0);
dinic();
sum=max(sum,ans);
}
cout<<sum<<'\n';
return 0;
}
CF1178H Stock Exchange - 前缀和优化建图 - 好题！
股票交易所里有 \(2n\) 种股票，每种股票有两个属性 \(a_i,b_i\)，在时刻 \(t\ge 0\)，第 \(i\) 种股票的价格为 \(a_i*\lfloor t\rfloor+b_i\)。
每个时刻可以进行任意次股票交易，在时刻 \(t\) 时能够把股票 \(i\) 换成股票 \(j\) 当且仅当股票 \(i\) 在时刻 \(t\) 的价格不小于股票 \(j\) 在时刻 \(t\) 的价格。
现在你手上有 \(1\) 到 \(n\) 号股票各一张，现在要求的是把这些股票换成 \(n+1\) 到 \(2n\) 号股票各一张的最早时刻，以及在最早换完股票前提下的最少交易次数。
\(1\le n\le 2200,0\le a_i,b_i\le 10^9\)
好题！
首先很容易想到二分答案，发现如果答案是 \(T\)，那么其实交换的时刻也就是 \(0,T\)，这样一定是不劣的。
于是我们就可以在 \(0\) 把每个股票换成 \(T\) 时刻最大的股票从而在 \(T\) 时刻任意交换，
而这样的贪心一定是不劣的，而实现起来直接用两个排序去解决，时间复杂度 \(\mathcal O(n \log^2n)\)。
于是乎第一问就解决了，现在来考虑第二问。
用同样的思路，我们很容易想到把一个点拆成两个，分别表示 \(0\) 和 \(T\) 时刻，
于是按照可以交换的关系建图，这样直接跑费用流即可。
但是发现这道题的空间是 \(16MB\)，显然是不行的。
考虑优化，
不难想到可以用前缀和优化建图，于是边数就变成了 \(O(n)\) 级别的，
最后跑一个费用流即可。（由于每次增广的流量一定是 \(1\)，所以可以做一些小优化，见代码）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5,inf=1e9;
int n,s,t,cnt=0,head[N],tot=-1,id1[N],id2[N],l,r,T,dis[N],lst[N],f[N],in[N],out[N],sum[N];
ll k[N],b[N],ans=0,pos[N];
struct edge{int v,nxt,w,c;}e[N<<1];
bool vis[N];
ll calc(int i,int x){return 1ll*x*k[i]+b[i];}
void add(int u,int v,int w,int c){
e[++tot]=(edge){v,head[u],w,c};head[u]=tot;
e[++tot]=(edge){u,head[v],0,-c};head[v]=tot;
}
bool spfa(){
for(int i=0;i<=cnt;i++) dis[i]=inf,vis[i]=false;
queue<int> q;q.push(s);
vis[s]=true;dis[s]=0;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w,c=e[i].c;
if(w&&dis[v]>dis[u]+c){
dis[v]=dis[u]+c;lst[v]=i;f[v]=u;
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return dis[t]!=inf;
}
void dinic(){
ans=0;
while(spfa()){
ans+=dis[t];
int u=t;
while(u!=s) --e[lst[u]].w,++e[lst[u]^1].w,u=f[u];
}
}
bool cmp1(const int &x,const int &y){return (b[x]==b[y])?(k[x]>k[y]):(b[x]<b[y]);}
bool chk(int T){
for(int i=1;i<=(n<<1);i++) id1[i]=id2[i]=i;
sort(id1+1,id1+(n<<1)+1,cmp1);
sort(id2+n+1,id2+(n<<1)+1,[&](int x,int y){return calc(x,T)<calc(y,T);});
ll mx=0;
for(int i=1;i<=(n<<1);i++){
mx=max(mx,calc(id1[i],T));
if(id1[i]<=n) pos[id1[i]]=mx;
}
sort(pos+1,pos+n+1);
for(int i=n;i>=1;i--)
if(pos[i]<calc(id2[i+n],T)) return false;
return true;
}
void sol(int T){
s=++cnt;t=++cnt;
for(int i=1;i<=(n<<1);i++){
id1[i]=id2[i]=i;
in[i]=++cnt;out[i]=++cnt;
if(i<=n) add(s,in[i],1,0);
else add(out[i],t,1,0);
add(in[i],out[i],inf,0);
}
sort(id1+1,id1+(n<<1)+1,cmp1);
sum[1]=in[id1[1]];
for(int i=2;i<=(n<<1);i++){
sum[i]=++cnt;
add(sum[i],sum[i-1],inf,0);
add(sum[i],in[id1[i]],inf,0);
add(in[id1[i]],sum[i-1],inf,1);
}
sort(id2+1,id2+(n<<1)+1,[&](int x,int y){return (calc(x,T)==calc(y,T))?x>y:calc(x,T)<calc(y,T);});
sum[1]=out[id2[1]];
for(int i=2;i<=(n<<1);i++){
sum[i]=++cnt;
add(sum[i],sum[i-1],inf,0);
add(sum[i],out[id2[i]],inf,0);
add(out[id2[i]],sum[i-1],inf,1);
}
dinic();
}
int main(){
/*2023.12.12 H_W_Y CF1178H Stock Exchange 二分+最小费用最大流*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
l=0,r=1e9+1;memset(head,-1,sizeof(head));tot=-1;
cin>>n;
for(int i=1;i<=(n<<1);i++) cin>>k[i]>>b[i];
while(l<r){
int mid=(l+r)/2;
if(chk(mid)) r=mid;
else l=mid+1;
}
if(l==1e9+1) cout<<"-1",exit(0);
sol(l);cout<<l<<' '<<ans<<'\n';
return 0;
}
P4249 [WC2007] 剪刀石头布 - 好题
在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到 \(A\) 胜过 \(B\)，\(B\) 胜过 \(C\) 而 \(C\) 又胜过 \(A\) 的有趣情况，不妨形象的称之为剪刀石头布情况。有的时候，无聊的人们会津津乐道于统计有多少这样的剪刀石头布情况发生，即有多少对无序三元组 \((A,B,C)\)，满足其中的一个人在比赛中赢了另一个人，另一个人赢了第三个人而第三个人又胜过了第一个人。注意这里无序的意思是说三元组中元素的顺序并不重要，将 \((A, B, C)\)、\((A, C, B)\)、\((B, A, C)\)、\((B, C, A)\)、\((C, A, B)\) 和 \((C, B, A)\) 视为相同的情况。
有 \(N\) 个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有 \(\frac{N*(N-1)}{2}\) 场比赛。比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。即给出已经发生的比赛结果，而你可以任意安排剩下的比赛的结果，以得到尽量多的剪刀石头布情况。
\(N \leq 100\)。
发现正着真的非常不好做啊。
题意就是一个三元环计数问题，但是正着一点也不好做。
所以现在我们考虑倒着来做，容易计算出 \(n\) 个点构成三元环的总个数是
\[\binom{n}{3}=\frac{n(n-1)(n-2)}{6} \]而当三个元素不能组成三元环时，一定是有一个点的 入度/出度 为 \(2\) 了。
那么我们现在只考虑入度（这样不会算重），
发现设一个点的入度时 \(x\)，那么它所在的三元组有 \(\binom{x}{2}\) 是不合法的。
于是答案就是
\[ans=\frac{n(n-1)(n-2)}{6} - \sum_{i=1}^n \binom{degree(i)}{2} \]可是现在又怎么求呢？
我们考虑差分一下，也就是考虑入度 \(+1\) 所造成的贡献，设当前入度为 \(x\)，那么
\[\binom{x+1}{2} - \binom{x}{2} = x \]于是我们把每一个的 \(x\) 作为费用，也就是 \(0,1,2,\dots\)，跑一次费用流就可以了。
如何建图？
由于一条边对应的两点只有一个点的入度会 \(+1\)，于是我们把每一条边也看作一个点。
- \(s\) 到边对应的点连一条容量为 \(1\)，费用为 \(0\) 的边。
- 边对应的点向它所连接的节点分别连容量为 \(1\)，费用为 \(0\) 的边，从而保证了只选一个。
- 每一个图中的节点向 \(t\) 建 \(n\) 条边，容量为 \(1\)，费用为 \(0,1,2,\dots\)。
于是就做完了。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=105,inf=1e9;
int n,head[N],tot=-1,cur[N],dis[N],ans=0,cnt=0,s,t,a[M][M],id[M][M],d[M];
bool vis[N];
struct edge{int v,nxt,w,c;}e[N<<1];
void add(int u,int v,int w,int c){
e[++tot]=(edge){v,head[u],w,c};head[u]=tot;
e[++tot]=(edge){u,head[v],0,-c};head[v]=tot;
}
bool spfa(){
for(int i=s;i<=t;i++) dis[i]=inf,vis[i]=false;
queue<int> q;q.push(s);
dis[s]=0;cur[s]=head[s],vis[s]=true;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w,c=e[i].c;
if(w&&dis[v]>dis[u]+c){
dis[v]=dis[u]+c;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return dis[t]!=inf;
}
int dfs(int u,int flow){
vis[u]=true;
if(u==t) return flow;
int res=flow;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v,w=e[i].w,c=e[i].c;
if(w&&!vis[v]&&dis[v]==dis[u]+c){
int nw=dfs(v,min(w,res));
res-=nw;e[i].w-=nw;e[i^1].w+=nw;
}
if(!res) break;
}
return flow-res;
}
void dinic(){
while(spfa()){
int nw=dfs(s,inf);
ans+=nw*dis[t];
}
}
int main(){
/*2023.12.12 H_W_Y P4249 [WC2007] 剪刀石头布 最小费用最大流*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;s=0,cnt=n;
memset(head,-1,sizeof(head));tot=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(j<=i) continue;
if(a[i][j]==1) ++d[i];
else if(a[i][j]==0) ++d[j];
else{
id[i][j]=++cnt;
add(cnt,i,1,0);add(cnt,j,1,0);add(s,cnt,1,0);
}
}
t=++cnt;ans=0;
for(int i=1;i<=n;i++){
if(d[i]>=2) ans+=(d[i]-1)*d[i]/2;
for(int j=d[i];j<n-1;j++) add(i,t,1,j);
}
dinic();
ans=n*(n-1)*(n-2)/6-ans;
cout<<ans<<'\n';
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i][j]==2)
for(int k=head[id[i][j]];k!=-1;k=e[k].nxt){
int v=e[k].v;
if(e[k].w==0){
if(v==i) a[i][j]=1,a[j][i]=0;
else a[i][j]=0,a[j][i]=1;
break;
}
}
for(int i=1;i<=n;cout<<'\n',i++) for(int j=1;j<=n;j++) cout<<a[i][j]<<' ';
return 0;
}
Conclusion
- 网络流可以通过 \(res=0\) 的剪枝大大减少复杂度。（P4177 [CEOI2008] order）
- 数组开小了也会 TLE。（P3227 [HNOI2013] 切糕）
- 网络流建图时我们可以考虑通过加一些边使得一些不合法的情况不会称为答案。（P3227 [HNOI2013] 切糕）
- 一些点强制匹配，一些点可以匹配的问题可以 黑白染色 之后直接跑 有源汇上下界可行流 判断即可。（CF1416F Showing Off）
- 对于有关矩形的问题，我们可以考虑 黑白染色 分组后解决或者 将 \(x,y\) 坐标分别作为左右部点 建图。（CF1416F + CF1592F2）
- 多种情况的问题我们可以先考虑那些情况不会用到。（CF1592F2 Alice and Recoloring 2）
- 注意精度问题，double 的二分的 eps 至少往下取两位。（P3705 [SDOI2017] 新生舞会）
- 有关最大的限制我们可以通过枚举答案转化到最小的限制来做。（[AGC031E] Snuke the Phantom Thief）
- 做题的时候要常常想到把 区间/矩形 的修改/权值通过某些方法转化到 一个点 上。（CF1178H Stock Exchange）
- 前缀和优化建图，可以大大减小空间复杂度。（CF1178H Stock Exchange）
- 一条边的两个节点只选一个的情况可以考虑将 边也看作点，分别向两个节点连边，容量 \(1\)，而 \(s\) 到边对于节点同样容量为 \(1\)。（P4249 [WC2007] 剪刀石头布）
- 计数问题要经常考虑容斥，将总方案数减去不合法方案数。（P4249 [WC2007] 剪刀石头布）
P3347 [ZJOI2015] 醉熏熏的幻想乡
傲娇少女幽香是一个很萌很萌的妹子，这些天幻想乡的大家都不知道为何还是拼命喝酒。很快酒就供不应求了，为了满足大家的需求，幽香决定在森林里酿酒。
经过调查，幽香发现森林里面有一些地方非常适合酿酒，有一些地方则非常适合存酒。幽香把这些适合酿酒的地方成为酿酒点，不妨认为有 \(n\) 个酿酒点，从 \(1\) 到 \(n\) 标号。同时也有 \(m\) 个适合存酒的地方，幽香将它们成为存酒点，从 \(1\) 到 \(m\) 标号。在一些酿酒点和存酒点之间存在通道，如果酿酒点 \(i\) 到存酒点 \(j\) 之间存在通道，那么 \(i\) 生产的酒就可以被运输到 \(j\)。
但是在一个地方酿酒是需要消耗幽香的魔力的，由于存在管理上的因素，在酿酒点 \(i\)，制造 \(x\) 升的酒，需要花费 \(a_i\cdot x^2+b_i\cdot x\) 的魔力，注意 \(x\) 不一定是一个非负整数，也可以是一个非负实数，同时在这个点最多只能制造 \(c_i\) 升的酒。每个存酒点 \(j\) 有一个容量 \(d_j\)，表示这个存酒点最多能存多少升的酒。
幽香打算存尽量多的酒，那么她需要再一些酿酒点生产一些酒并且通过通道将酒运送到存酒点。当然幽香想要节省自己的魔力，所以想让你帮忙算出在满足要求的情况下，最少花费的魔力是多少？
\(1\leq n\leq100\)，\(1\leq m\leq100\)。
不能要了，已经把前面严格偏序了。（所以它与 网络流学习笔记 是并列关系了）
花了整整一个晚上+上午，但是真的好妙。
首先乍一看好像是费用流的板子，但是发现费用是二次函数。
而第一问是很好解决的，直接跑一次最大流即可，但是怎么算费用呢？
二次函数首先是不好处理的，所以我们考虑把它分成很多个区间，
也就说想要把流量的精度变得尽可能小，假设每一次增广的流量是 \(\Delta t\)，
于是我们就可以将一个点向外连 \(\frac{c_i}{\Delta t}\) 条边，每条边的费用分别是每个 \(\Delta t\) 区间中所增加的费用，
只要我们把 \(\Delta t\) 分得足够小，那么精度是没有问题的，
也就说 \(\Delta t \to 0^+\) 时，我们可以得到答案，而此时每一次的费用就是原函数的导函数 \(f'(x)=2ax+b\)。
但是显然时间复杂度是不允许的，不过理论上是可以拿不少分的。
那么我们现在考虑如何优化？
显然按照上面的思路是不好做的，于是我们考虑费用流的本质。
发现我们每次是找一条最短路，然后增广过去，也就是把最短路流满。
而在这个图中，发现只有 \(s\) 和酿酒点之间是有费用的，所以我们每一次其实是找了一个瞬间费用最小的酿酒点流下去。
所以对于每一个酿酒点，它的费用会从某一费用开始增加，而会在某一费用停止，
不从 \(0\) 开始是因为最初 \(b_i\) 的值，而停止增加是因为流量已经流满了 \(c_i\)，或者造的就运不出去了。
而对于 \(a_i=0\) 的情况我们需要特殊考虑（后面再分析）。
现在我们记每一条边在 瞬间 的费用为 瞬时费用，也就是我们的导函数 \(f_i'(x)=2 a_i x+b_i\)，
发现这是一次函数关系，那么如果我们求出来 瞬时费用与流量 的关系，那么它与 \(y\) 轴围成的面积就是答案。
现在我们考虑当前的 瞬时费用 为 \(\lambda\)，于是对于每一条边，有了流量的上界：\(L_i= \min(c_i,\frac{\lambda-b_i}{2a_i})\)。
\(\frac{\lambda -b_i}{2a_i}\) 的由来：
我们假设此时流量 \(x\) 最大，那么满足
\[\begin{align} 2a_ix+b_i & =\lambda\\ x& = \frac{\lambda -b_i}{2a_i} \end{align} \]
注意要特判 \(a_i = 0\) 的情况。
于是现在我们考虑求出 流量与瞬时费用 的折线 \(T\)。
而这是可以通过每条边是否满流和与 \(b_i\) 的关系就可以求出。
- \(\lambda \le b_i\)，那么根本不存在这条边，不产生贡献。
- 当前边满流且 \(\lambda \gt b_i\)，
- 若 \(L_i \le c_i\)，那么流量会随 \(\lambda\) 增大而增大，而当 \(\lambda\) 更小的时候也会满流。
- 若 \(L_i \gt c_i\)，那么 \(L_i\) 会一直 \(= c_i\)，此时 \(x_i =c_i\)
- 当前边不满流直接加上贡献即可。
这我们就可以求出 \(T\) 在 \(\lambda\) 处 \(\sum x_i\) 关于 \(\lambda\) 的函数。
分析到这里我们发现，
函数变换的时候当且仅当一条边启用，即 \(\lambda = b_i\) 时，
或者一条边满流/顶到上界的时候，而由于 \(b_i \le 3\)，所以我们得到的折线 \(T\) 最多只有 \(2n\) 个拐点。
而为了放防止每次枚举到的 \(\lambda\) 不是拐点，
我们对 \(\lambda\) 进行随机的扰动即可。
于是我们最终想得到的时折线 \(T\) 的左右拐点，设他们的横坐标（也就是瞬间费用）是 \({\lambda_1,\lambda_2 \dots}\)。
那么整个折线的图像是这样的（图来自题解）
于是黄色的面积就是答案。（也就是瞬时费用和流量的乘积）
发现 \(0\) 一定是一个拐点，
而如果有一个 \(a_i=0\) 的酿酒点，那么这条线会直线上升，也就是与 \(y\) 轴平行，这是需要直接提出来讨论的。
求这个折线，我们发现它是一个上凸的形式，
于是我们直接分治就可以找到这些横坐标了。
具体实现是这样的：
void sol(auto l,auto r){
if(l==r) return;
frac lambda=(r.se-l.se)/(l.fi-r.fi);
auto mid=dinic(lambda.val()+eps);
if(mid==r) return p.pb(lambda),void();
sol(l,mid);sol(mid,r);
}
找到所有的 \(\lambda\) 之后，求面积就简单很多了，
只需要考虑两种情况：\(0,1,2,3\) 时的与 \(y\) 轴平行的矩形面积，和后面的梯形面积。
直接用公式算就可以了。
for(int i=1;i<(int)p.size();i++){
auto l=dinic(p[i].val()-eps),r=dinic(p[i].val()+eps);
ans=ans+p[i]*(r.se-l.se+(r.fi-l.fi)*p[i]);//矩形面积
ans=ans+(p[i]+p[i-1])*(p[i]-p[i-1])*l.fi*frac(1,2);//梯形面积
}
具体实现中就直接写一个分数类从而尽量减小误差，
函数 dinic 就是求当瞬时费用为 \(\lambda\) 时我们在折线上面的函数表达式。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define fi first
#define se second
#define pb push_back
ll gcd(ll a,ll b){return (b==0)?a:gcd(b,a%b);}
struct frac{
ll a,b;
frac(ll x=0,ll y=1){ll g=gcd(x,y);a=x/g,b=y/g;}
bool operator == (const frac &x)const {return a*x.b==b*x.a;}
frac operator + (const frac &x)const {return frac(a*x.b+x.a*b,b*x.b);}
frac operator - (const frac &x)const {return frac(a*x.b-x.a*b,b*x.b);}
frac operator * (const frac &x)const {return frac(a*x.a,b*x.b);}
frac operator / (const frac &x)const {return frac(a*x.b,b*x.a);}
db val(){return 1.0*a/b;}
void prt(){cout<<a<<"/"<<b<<'\n';}
}ans;
const int inf=1e9,N=205,M=2e3+5;
const db eps=1e-7,feps=1e-8;
struct flow{
int head[N],tot=-1,cur[N],lv[N],t;
struct edge{int v,nxt;db w;}e[M<<1];
bool vis[N];
void init(){memset(head,-1,sizeof(head));tot=-1;}
void add(int u,int v,db w){
e[++tot]=(edge){v,head[u],w};head[u]=tot;
e[++tot]=(edge){u,head[v],0};head[v]=tot;
}
db dfs(int u,db fl){
if(u==t) return fl;
db res=fl;
for(int &i=cur[u];i!=-1;i=e[i].nxt){
int v=e[i].v;db w=e[i].w;
if(w>=feps&&lv[v]==lv[u]+1){
db c=dfs(v,min(res,w));
res-=c;e[i].w-=c;e[i^1].w+=c;
}
if(res<feps) break;
}
return fl-res;
}
void wrk(int s,int T){
t=T;
while(1){
memset(lv,-1,sizeof(lv));
queue<int> q;q.push(s);
cur[s]=head[s];lv[s]=0;vis[s]=true;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].v;db w=e[i].w;
if(w>=feps&&lv[v]==-1){
lv[v]=lv[u]+1;cur[v]=head[v];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
if(lv[t]==-1) break;
dfs(s,inf);
}
}
}g;
int n,m,cnt,a[N],b[N],c[N],d[N],e[N][N];
vector<frac> p;
pair<frac,frac> dinic(db lambda){
g.init();
for(int i=1;i<=n;i++)
if(b[i]<lambda){
if(!a[i]) g.add(0,i,c[i]);
else g.add(0,i,min(1.0*c[i],1.0*(lambda-b[i])/(2*a[i])));
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(e[i][j]) g.add(i,j+n,inf);
for(int i=1;i<=m;i++) g.add(i+n,cnt,d[i]);
g.wrk(0,cnt);
frac K,B;
for(int i=1;i<=n;i++)
if(b[i]<lambda&&g.lv[i]==-1){
if(!a[i]) B=B+frac(c[i]);
else if(2*a[i]*c[i]+b[i]<lambda) B=B+frac(c[i]);
else K=K+frac(1,2*a[i]),B=B-frac(b[i],2*a[i]);
}
for(int i=1;i<=m;i++) if(g.lv[i+n]!=-1) B=B+frac(d[i]);
return make_pair(K,B);
}
void sol(auto l,auto r){
if(l==r) return;
frac lambda=(r.se-l.se)/(l.fi-r.fi);
auto mid=dinic(lambda.val()+eps);
if(mid==r) return p.pb(lambda),void();
sol(l,mid);sol(mid,r);
}
int main(){
/*2023.12.13 H_W_Y P3347 [ZJOI2015] 醉熏熏的幻想乡 最小费用最大流*/
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;cnt=n+m+1;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
for(int i=1;i<=m;i++) cin>>d[i];
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>e[i][j];
p.pb(frac());
for(int t=1;t<4;t++){
sol(dinic(t-1+eps),dinic(t-eps));
p.pb(frac(t));
}
sol(dinic(3+eps),dinic(inf));
for(int i=1;i<(int)p.size();i++){
auto l=dinic(p[i].val()-eps),r=dinic(p[i].val()+eps);
ans=ans+p[i]*(r.se-l.se+(r.fi-l.fi)*p[i]);
ans=ans+(p[i]+p[i-1])*(p[i]-p[i-1])*l.fi*frac(1,2);
}
cout<<dinic(inf).se.val()<<'\n';ans.prt();
return 0;
}