#include <bits/stdc++.h>
using namespace std;

const int N=4e3+10 ,M=4e4+10, INF=1e8;
int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y; cc[tot]=c; ww[tot]=d; nxt[tot]=head[x]; head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],incf[N],pre[N];
bool vis[N];
int n,m,S,T;

bool spfa()
{
    int hh=0,tt=1;
    memset(d,0x7f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S,d[S]=0,incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;
        vis[x]=0;
        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]>d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        cost+=d[T]*tmp;
        for(int i=T;i!=S;i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d",&n,&m);
    S=n+5,T=S+1;
    memset(head,-1,sizeof head);
    int lst=0;
    /*由于本题带下界的边组成了一条链，所以C(入)就是上一天的人数下界，C(出)就是这一天的人数下界*/
    for(int i=1;i<=n;i++)
    {
        int r;
        scanf("%d",&r);//读入当前人数
        add(i,i+1,INF-r,0);
        if(lst>r) add(S,i,lst-r,0);
        else if(lst<r) add(i,T,r-lst,0);//向源汇点连边
        lst=r;
    }
    add(S,n+1,lst,0);//最后一个点特殊情况

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(b+1,a,INF,c);
    }

    printf("%d",EK());//直接求G'最小费用最大流
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=2e6+10,INF=1e8+10;

int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y, cc[tot]=c; ww[tot]=d, nxt[tot]=head[x], head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],incf[N],pre[N];
bool vis[N];
int n,p,fn,f,sn,s,S,T;

bool spfa()
{
    int hh=0,tt=1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S; d[S]=0; incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;
        vis[x]=0;
        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]>d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        cost+=d[T]*tmp;
        for(int i=T;i!=S;i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d%d%d%d%d",&n,&p,&fn,&f,&sn,&s);
    memset(head,-1,sizeof head);
    S=0,T=n*2+10;
    /*1~n 旧毛巾，n+1~2n 新毛巾*/
    for(int i=1;i<=n;i++)
    {
        int r;
        scanf("%d",&r);
        add(S,i,r,0);
        add(n+i,T,r,0);//与限制 r 有关的边
    }
    for(int i=1;i<=n;i++)
    {
        add(S,n+i,INF,p);//购买

        if(i+fn<=n) add(i,n+i+fn,INF,f);
        if(i+sn<=n) add(i,n+i+sn,INF,s);//快洗部和慢洗部

        if(i<n) add(i,i+1,INF,0);//放到下一天
    }

    printf("%d",EK());
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+10,M=1e6+10,INF=1e8+10;

int n,m,A,B,S,T;
int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y; cc[tot]=c; ww[tot]=d; nxt[tot]=head[x]; head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],incf[N],pre[N];
bool vis[N];

int get(int x,int y)//坐标->点编号
{
    return x*15+y+1;
}

bool spfa()
{
    int hh=0,tt=1;
    memset(d,-0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S; d[S]=0; incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;
        vis[x]=0;

        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]<d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        cost+=d[T]*tmp;
        for(int i=T; i!=S; i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d%d%d",&A,&B,&n,&m);
    memset(head,-1,sizeof head);
    S=N-1,T=N-2;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<m;j++)//(i,j)->(i,j+1)
        {
            int x;
            scanf("%d",&x);
            add(get(i,j),get(i,j+1),1,x);
            add(get(i,j),get(i,j+1),INF,0);
        }
    }
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<n;j++)//(j,i)->(j+1,i)
        {
            int x;
            scanf("%d",&x);
            add(get(j,i),get(j+1,i),1,x);
            add(get(j,i),get(j+1,i),INF,0);
        }
    }
    for(int i=1;i<=A;i++)
    {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        add(S,get(x,y),k,0);
    }
    for(int i=1;i<=B;i++)
    {
        int r,x,y;
        scanf("%d%d%d",&r,&x,&y);
        add(get(x,y),T,r,0);
    }
    printf("%d",EK());
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N=2e4+10, M=4e5+10, INF=1e8+10;

int n,k,S,T;
int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y; cc[tot]=c; ww[tot]=d; nxt[tot]=head[x]; head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],pre[N],incf[N];
bool vis[N];

inline int get(int x,int y)
{
    return (x-1)*n+y;
}

bool spfa()
{
    int hh=0,tt=1;
    memset(d,-0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S; d[S]=0,incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;
        vis[x]=0;

        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]<d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        cost+=tmp*d[T];
        for(int i=T;i!=S;i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d",&n,&k);
    memset(head,-1,sizeof head);
    S=0,T=n*n*2+100;
    int B=n*n+5;
    add(S,1,k,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            int pos=get(i,j);
            add(pos,B+pos,1,x);
            add(pos,B+pos,INF,0);

            if(i+1<=n) add(B+pos,get(i+1,j),INF,0);
            if(j+1<=n) add(B+pos,get(i,j+1),INF,0);
        }
    }
    add(B+get(n,n),T,k,0);

    printf("%d",EK());
    return 0;
}

这篇代码在Acwing上表现良好，在洛谷上T得飞起。

数据范围一样的情况下应该都能够过才对。

不应该是我板子写错了呀

求捉虫 优化了一个下午了qwq

#include<bits/stdc++.h>
using namespace std;

const int N=2e4+10,M=3e5+10,INF=1e8;

int n,m,S,T;
int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y; cc[tot]=c; ww[tot]=d; nxt[tot]=head[x]; head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d;nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],incf[N],pre[N];
bool vis[N];

int get(int x,int y)//x行y列
{
    return (2*m+x)*x/2+y;
}

bool spfa()
{
    int hh=0,tt=1;
    memset(d,-0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S; d[S]=0; incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;
        vis[x]=0;

        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]<d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        cost+=d[T]*tmp;
        for(int i=T; i!=S; i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d",&m,&n);
    memset(head,-1,sizeof head);
    S=0,T=N-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m+i-1;j++)
        {
            int x;
            scanf("%d",&x);
            int pos=get(i,j);
            add(pos,605+pos,1,x);//拆点
            add(605+pos,get(i+1,j),1,0);
            add(605+pos,get(i+1,j+1),1,0);
            if(i==1) add(S,pos,1,0);
            if(i==n) add(605+pos,T,1,0);
        }
    }

    printf("%d\n",EK());
    for(int i=0;i<tot;i+=2)
    {
        int y=ver[i],x=ver[i^1];
        if(y==605+x||y==T) cc[i]=INF,cc[i^1]=0;
        else cc[i]=1,cc[i^1]=0;
    }
    printf("%d\n",EK());
    for(int i=0;i<tot;i+=2)
    {
        int x=ver[i^1];
        if(x!=S) cc[i]=INF,cc[i^1]=0;
        else cc[i]=1,cc[i^1]=0;
    }
    printf("%d\n",EK());
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int N=2e4+10,M=3e5+10,INF=1e8;

int n,m,S,T;
int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y; cc[tot]=c; ww[tot]=d; nxt[tot]=head[x]; head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d;nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],incf[N],pre[N];
bool vis[N];

int get(int x,int y)//x行y列
{
    return (2*m+x)*x/2+y;
}

bool spfa()
{
    int hh=0,tt=1;
    memset(d,-0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S; d[S]=0; incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;//循环队列
        vis[x]=0;

        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]<d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;//这里为了简洁+防止数组越界，我们将tt设高一位
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        cost+=d[T]*tmp;
        for(int i=T; i!=S; i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d",&m,&n);
    memset(head,-1,sizeof head);
    S=0,T=N-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m+i-1;j++)
        {
            int x;
            scanf("%d",&x);
            int pos=get(i,j);
            add(pos,605+pos,1,x);//拆点
            add(605+pos,get(i+1,j),1,0);
            add(605+pos,get(i+1,j+1),1,0);
            if(i==1) add(S,pos,1,0);
            if(i==n) add(605+pos,T,1,0);
        }
    }

    printf("%d\n",EK());
    for(int i=0;i<tot;i+=2)
    {
        int y=ver[i],x=ver[i^1];
        if(y==605+x||y==T) cc[i]=INF,cc[i^1]=0;
        else cc[i]=1,cc[i^1]=0;
    }
    printf("%d\n",EK());
    for(int i=0;i<tot;i+=2)
    {
        int x=ver[i^1];
        if(x!=S) cc[i]=INF,cc[i^1]=0;
        else cc[i]=1,cc[i^1]=0;
    }
    printf("%d\n",EK());
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N=510,M=8e4+10,INF=1e8;

int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y; cc[tot]=c; ww[tot]=d; nxt[tot]=head[x]; head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d;nxt[tot]=head[y]; head[y]=tot++;
}
int q[N+5],d[N],incf[N],pre[N];
bool vis[N];
int n,S,T;

bool spfa()
{
    int hh=0,tt=1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S; d[S]=0; incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;//循环队列
        vis[x]=0;

        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]>d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;//这里为了简洁+防止数组越界，我们将tt设高一位
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()//用引用来解决传出两个参数的问题
{
    int flow=0,cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        flow+=tmp; cost+=tmp*d[T];
        for(int i=T; i!=S; i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
    return cost;
}

int main()
{
    scanf("%d",&n);
    memset(head,-1,sizeof head);
    S=0,T=2*n+1;
    /*1~n人，n+1~2n工作*/
    for(int i=1;i<=n;i++)
    {
        add(S,i,1,0);
        add(n+i,T,1,0);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            add(i,n+j,1,x);
        }
    }

    printf("%d\n",EK());
    for(int i=0;i<tot;i+=2)
    {
        cc[i]+=cc[i^1]; cc[i^1]=0;
        ww[i]=-ww[i]; ww[i^1]=-ww[i^1];
    }
    printf("%d",-EK());
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N=510, M=1e5+10, INF=1e8+10;

int n,S,T;
int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y; cc[tot]=c; ww[tot]=d; nxt[tot]=head[x]; head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d; nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],pre[N],incf[N];
bool vis[N];
int poi[N];

bool spfa()
{
    int hh=0,tt=1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S; d[S]=0, incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;
        vis[x]=0;

        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]>d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int flow=0,cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        flow+=tmp; cost+=d[T]*tmp;
        for(int i=T;i!=S;i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
    return cost;
}

int main()
{
    scanf("%d",&n);
    memset(head,-1,sizeof head);
    S=0,T=n+1;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",poi+i);
        sum+=poi[i];
    }
    int a_=sum/n;
    for(int i=1;i<=n;i++)
    {
        if(poi[i]>a_) add(S,i,poi[i]-a_,0);
        if(poi[i]<a_) add(i,T,a_-poi[i],0);
        if(i-1>0) add(i,i-1,INF,1);
        else add(i,n,INF,1);
        if(i+1<=n) add(i,i+1,INF,1);
        else add(i,1,INF,1);
    }

    printf("%d",EK());
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 

const int N=2e6+10,M=N<<1;

int head[N],ver[M],nxt[M],tot=0;
void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int n,m;
int poi[N];
int id[N],nwpoi[N],cnt=0;
int dpt[N],size_[N],top[N]; //每个点的深度，每个点为根的子树大小，所在重链的顶点

int fa[N],son[N];//父节点，重儿子 

ll tree[N<<2],lazy[N<<2];//线段树相关 

void dfs1(int x,int f)  //寻找重儿子 
{
    dpt[x]=dpt[f]+1; //记录深度 
    fa[x]=f; //记录父节点 
    size_[x]=1; //子树至少有他自己 
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y==f) continue;
        dfs1(y,x);
        size_[x]+=size_[y];     //子树大小加起来 
        if(size_[son[x]]<size_[y]) son[x]=y;    //打擂台记录重儿子 
    }
}

void dfs2(int x,int t)  //t:当前重链的起点是谁 
{
    id[x]=++cnt; //记录DFS序 
    nwpoi[cnt]=poi[x]; //节点的权值重新排序 
    top[x]=t; //记录这个节点所在重链的起点 
    if(!son[x]) return ;
    dfs2(son[x],t); //优先搜索重儿子，重儿子一定在当前这条重链内 
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);  //轻儿子一定是另外一条重链的开头 
    }
} 

inline void push_up(int node)
{
    tree[node]=tree[node<<1]+tree[node<<1|1];
}

void func(int node,int start,int end,int k)
{
    lazy[node]=lazy[node]+k;
    tree[node]=tree[node]+k*(end-start+1);
}
void push_down(int node,int start,int end)
{
    if(lazy[node]==0) return;
    ll mid=start+end>>1;
    int lnode=node<<1;
    int rnode=node<<1|1;
    func(lnode,start,mid,lazy[node]);
    func(rnode,mid+1,end,lazy[node]);
    lazy[node]=0;
}

void build(int node,int start,int end)
{
    lazy[node]=0;
    if(start==end)
    {
        tree[node]=nwpoi[start];
        return ;
    }
    int mid=start+end>>1;
    int lnode=node<<1;
    int rnode=node<<1|1;
    build(lnode,start,mid);
    build(rnode,mid+1,end);

    push_up(node);
}

void update(int node,int start,int end,int l,int r,int val)
{
    if(l<=start&&end<=r)
    {
        tree[node]+=val*(end-start+1);
        lazy[node]+=val;
        return ;
    }
    push_down(node,start,end);

    int mid=start+end>>1;
    int lnode=node<<1;
    int rnode=node<<1|1;

    if(l<=mid) update(lnode,start,mid,l,r,val);
    if(r>mid) update(rnode,mid+1,end,l,r,val);

    push_up(node);
}

ll query(int node,int start,int end,int l,int r)
{
    if(end<l||start>r) return 0;
    if(l<=start&&end<=r)
        return tree[node];

    push_down(node,start,end);

    int mid=start+end>>1;
    int lnode=node<<1;
    int rnode=node<<1|1;
    ll lsum=query(lnode,start,mid,l,r);
    ll rsum=query(rnode,mid+1,end,l,r);
    return lsum+rsum;

    push_up(node);
}

void update_path(int x,int y,int k)
{
    while(top[x]!=top[y])   //如果不在同一重链 
    {
        if(dpt[top[x]]<dpt[top[y]]) swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];   //向上跳，直到位于同一重链 
    }
    if(dpt[x]<dpt[y]) swap(x,y);
    update(1,1,n,id[y],id[x],k);
}

ll query_path(int x,int y)
{
    ll res=0;
    while(top[x]!=top[y])
    {
        if(dpt[top[x]]<dpt[top[y]]) swap(x,y);
        res+=query(1,1,n,id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(dpt[x]<dpt[y]) swap(x,y);
    res+=query(1,1,n,id[y],id[x]);
    return res;
}

void update_tree(int x,int k)
{
    int l=id[x],r=id[x]+size_[x]-1; //子树的dfs序是连续的一段 
    update(1,1,n,l,r,k);
}

ll query_tree(int x)
{
    int l=id[x],r=id[x]+size_[x]-1;
    return query(1,1,n,l,r);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",poi+i);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    dfs1(1,1);
    dfs2(1,1);
    build(1,1,n);

    scanf("%d",&m);
    while(m--)
    {
        int k,x,y,val;
        scanf("%d%d",&k,&x);
        if(k==1)
        {
            scanf("%d%d",&y,&val);
            update_path(x,y,val);   //修改路径上的节点权值 
        }
        else if(k==2)
        {
            scanf("%d",&val);
            update_tree(x,val);     //修改子树上的节点权值 
        }
        else if(k==3)
        {
            scanf("%d",&y);
            ll ans=query_path(x,y);     //询问路径权值和
            printf("%lld\n",ans); 
        }
        else if(k==4)
        {
            ll ans=query_tree(x);       //询问子树权值和 
            printf("%lld\n",ans);
        }
    }
    return 0; 
}

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+10,M=2e5+10,INF=1e8;

int n,m,S,T;
int head[N],ver[M],nxt[M],cc[M],ww[M],tot=0;
void add(int x,int y,int c,int d)
{
    ver[tot]=y; cc[tot]=c; ww[tot]=d; nxt[tot]=head[x]; head[x]=tot++;
    ver[tot]=x; cc[tot]=0; ww[tot]=-d;nxt[tot]=head[y]; head[y]=tot++;
}
int q[N],d[N],incf[N],pre[N];
bool vis[N];

bool spfa()
{
    int hh=0,tt=1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S; d[S]=0; incf[S]=INF;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N) hh=0;
        vis[x]=0;
        for(int i=head[x];~i;i=nxt[i])
        {
            int y=ver[i];
            if(cc[i] && d[y]>d[x]+ww[i])
            {
                d[y]=d[x]+ww[i];
                pre[y]=i;
                incf[y]=min(cc[i],incf[x]);
                if(!vis[y])
                {
                    q[tt++]=y;
                    if(tt==N) tt=0;
                    vis[y]=1;
                }
            }
        }
    }
    return incf[T]>0;
}

void EK(int& flow,int& cost)
{
    flow=cost=0;
    while(spfa())
    {
        int tmp=incf[T];
        flow+=tmp; cost+=tmp*d[T];
        for(int i=T;i!=S;i=ver[pre[i]^1])
        {
            cc[pre[i]]-=tmp;
            cc[pre[i]^1]+=tmp;
        }
    }
}

int main()
{
    scanf("%d%d",&m,&n);
    S=0,T=n+m+10;
    memset(head,-1,sizeof head);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        add(S,i,x,0);
    }
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        add(m+i,T,x,0);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            add(i,m+j,INF,x);
        }
    }
    int flow,cost;
    EK(flow,cost);
    printf("%d\n",cost);
    for(int i=0;i<tot;i+=2)
    {
        cc[i]+=cc[i^1]; cc[i^1]=0;
        ww[i]=-ww[i]; ww[i^1]=-ww[i^1];
    }
    EK(flow,cost);
    printf("%d",-cost);
    return 0;
}