lyzlyz?lyzlyz!

惯例开坑。

任务栏：

订正了几题？3/3

BZOJ刷题量？306/300

撒花~~~~~~

谜之声：这里的网络流包括最大流、最小割、费用流、有上下界网络流等。

好吧废话不说直接上模板。

【模板】

int bfs(){
    int l=1,r=1;
    memset(dis,-1,sizeof dis);
    h[1]=S;dis[S]=0;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]<0){
                dis[v]=dis[u]+1;
                h[++r]=v;
            }
        }
        l++;
    }
    if (dis[T]<0)return 0;else return 1;
}
int dfs(int u,int aug){
    if (u==T)return aug;
    int flow=0;
    for (int e=head[u];e;e=next[e]){
        int v=vet[e];
        if (size[e]&&dis[v]==dis[u]+1){
            int tmp=dfs(v,min(aug-flow,size[e]));
            flow+=tmp;
            size[e]-=tmp;
            size[e^1]+=tmp;
            if (flow==aug)return flow;
        }
    }
    if (!flow)dis[u]=-1;
    return flow;
}

int spfa(){
    int l=1,r=1;
    for (i=0;i<=2*n+1;i++)dis[i]=inf;
    dis[S]=0;h[1]=S;rem[S]=inf;flag[S]=1;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]>dis[u]+len[e]){
                dis[v]=dis[u]+len[e];
                pre[v][0]=u;pre[v][1]=e;
                rem[v]=min(rem[u],size[e]);
                if (!flag[v]){
                    flag[v]=1;
                    h[++r]=v;
                }
            }
        }
        l++;
        flag[u]=0;
    }
    if (dis[T]==inf)return 0;
    ans+=dis[T]*rem[T];
    int u=T;
    while (u!=S){
        size[pre[u][1]]-=rem[T];
        size[pre[u][1]^1]+=rem[T];
        u=pre[u][0];
    }
    return 1;
}

【例题】

BZOJ2756 给你一个n*m的矩阵，每个格子一开始有一个数值，你每次操作可以使相邻两个格子+1，问最少几次操作可以使矩阵上的数相同。

假设已经确定了最后每个格子上的数D，那么黑白染色，源连黑点，白点连汇，流量均为D-a[i][j]，跑最大流看是否满流就知道了是否可行。

那么如何确定D呢？若n*m为奇数，即黑白点个数不同，那么发现：每次操作黑白点点权各+1，即黑白点的点权之差始终相等，那么D就是黑白点权之差。

若n*m为偶数，如果D可行，那么D+1显然可行，所以可以二分。

BZOJ1927 n个点m条边的有向无环图，可以选择瞬移到某个点，代价为点权a[i]，或从某个点走到另一个点，代价为边权b[i]，要求每个点仅经过一次，问最小代价。

类似最小路径覆盖，每个点裂出两个u,u'，源连u，流量为1，费用为0；源连u'，流量为1，费用为a[i]；u连v'，流量为1，费用为b[i]，这样就满足了题目的限制条件。

跑费用流即可。

BZOJ2324 题意太长，请自行搜索。

首先要跑一遍最短路，dis[i][j]表示从i到j(i<j)经过编号小于j的点的最短路，可以用floyed解决。

那么就是k条路径最小覆盖，建图与上题类似，但是没有源到u‘的边，源连0的流量为k。

BZOJ1061 我是传送门

BZOJ1070 n辆车m个维修员，每个维修员修完一辆车的时间均不同，求顾客的平均等待时间。

考虑维修员i修编号为j的车，且该车是倒数第k辆i修的车，那么对答案的贡献就是a[i][j]*k。

那么动态加边，源连维修员，流量为1，费用为0；维修员连车，流量为1，费用为a[i][j]；车连汇，流量为1，费用为0。

如果一个维修员被流过，就新建一个点与所有车连一条边，流量为1，费用为a[i][j]*k。

（由于此题数据范围太小直接暴力加完就行。。。）

BZOJ2879 n个厨师m道菜，每个厨师做一道菜的时间均不同，每道菜要b[i]份，求总等待时间。

与上题类似，菜连汇的流量改成b[i]就可以了。

BZOJ2561 n个点m条边的无向图，给定一条边，问最少删去多少条边使得给定的边既在最小生成树上又在最大生成树上。

考虑kruscal算法，对于边权小于给定边的那些边，若全部加上后u->v仍然不连通，那么给定边一定在最小生成树上。最大生成树同理。

那么只要两次最小割就可以了。

BZOJ1412 n行m列的矩阵，每个格子是狼或羊或空地，要用栅栏将狼与羊隔开，求栅栏的最小周长。

源连狼，流量为inf；羊连汇，流量为inf；格子互相联通，流量为1，跑最小割即可。

BZOJ1497 n个产品，获利为a[i]，需要机器b[i],c[i]完成；每个机器都有一个购置代价w[i]，求最大获利。

源连机器，流量为w[i]，机器连产品，流量为inf；产品连汇，流量为a[i]。求最小割，即要么购置机器，要么放弃获利。答案为获利总和-最小割。

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=100010;
const ll inf=1ll<<50;
int cas,n,m,i,j,edgenum;
ll size[M];
int head[M],vet[M],next[M],h[M],dis[M];
int a[50][50];
int u[4]={0,0,-1,1},v[4]={1,-1,0,0};
ll max(ll x,ll y){if (x>y)return x;else return y;}
ll min(ll x,ll y){if (x<y)return x;else return y;}
int point(int x,int y){
    return (x-1)*m+y;
}
void addedge(int x,int y,ll ch){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=ch;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=0;
}
void buildgraph(ll x){
    int i,j,k;
    edgenum=1;
    memset(head,0,sizeof head);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if ((i+j)%2)addedge(point(i,j),n*m+2,x-a[i][j]);
                else addedge(n*m+1,point(i,j),x-a[i][j]);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (!((i+j)%2)){
                for (k=0;k<4;k++){
                    int x=i+u[k],y=j+v[k];
                    if (x&&x<=n&&y&&y<=m)addedge(point(i,j),point(x,y),inf*n*m);
                }
            }
}
int bfs(){
    memset(dis,-1,sizeof dis);
    int l=1,r=1;
    h[1]=n*m+1,dis[n*m+1]=0;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]<0){
                dis[v]=dis[u]+1;
                h[++r]=v;
            }
        }
        l++;
    }
    if (dis[n*m+2]<0)return 0;else return 1;
}
ll dfs(int u,ll aug){
    if (u==n*m+2)return aug;
    ll flow=0;
    for (int e=head[u];e;e=next[e]){
        int v=vet[e];
        if (size[e]&&dis[v]==dis[u]+1){
            ll tmp=dfs(v,min(aug-flow,size[e]));
            size[e]-=tmp;
            size[e^1]+=tmp;
            flow+=tmp;
            if (flow==aug)return flow;
        }
    }
    if (!flow)dis[u]=-1;
    return flow;
}
int main(){
    scanf("%d",&cas);
    while (cas--){
        scanf("%d%d",&n,&m);
        ll sum=0;
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++)scanf("%d",&a[i][j]),sum+=a[i][j];
        ll D=0;
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++)
                if ((i+j)%2)D-=a[i][j];else D+=a[i][j];
        if (n%2&&m%2){
            buildgraph(D);
            ll ans=0;
            while (bfs())ans+=dfs(n*m+1,inf*n*m);
            if (ans==D*n*m-sum>>1)printf("%lld\n",ans);else puts("-1");
        }else{
            if (D){puts("-1");continue;}
            ll l=0,r=inf;
            for (i=1;i<=n;i++)
                for (j=1;j<=m;j++)
                    l=max(l,a[i][j]);
            while (l<r){
                ll mid=l+r>>1,ans=0;
                buildgraph(mid);
                while (bfs())ans+=dfs(n*m+1,inf*n*m);
                if (ans==mid*n*m-sum>>1)r=mid;else l=mid+1;
            }
            printf("%lld\n",l*n*m-sum>>1);
        }
    }
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=2000000000;
int head[M],vet[M],next[M],size[M],len[M],h[M*30],flag[M],dis[M],rem[M],pre[M][2];
int n,m,i,x,y,ch,ans,edgenum;
void addedge(int x,int y,int z,int w){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=z;
    len[edgenum]=w;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=0;
    len[edgenum]=-w;
}
int spfa(){
    int l=1,r=1;
    for (i=0;i<=2*n+1;i++)dis[i]=inf;
    dis[0]=0;h[1]=0;rem[0]=inf;flag[0]=1;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]>dis[u]+len[e]){
                dis[v]=dis[u]+len[e];
                pre[v][0]=u;pre[v][1]=e;
                rem[v]=min(rem[u],size[e]);
                if (!flag[v]){
                    flag[v]=1;
                    h[++r]=v;
                }
            }
        }
        l++;
        flag[u]=0;
    }
    if (dis[n*2+1]==inf)return 0;
    ans+=dis[n*2+1]*rem[n*2+1];
    int u=2*n+1;
    while (u){
        size[pre[u][1]]-=rem[n*2+1];
        size[pre[u][1]^1]+=rem[n*2+1];
        u=pre[u][0];
    }
    return 1;
}
int main(){
    //freopen("1.out","w",stdout);
    edgenum=1;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        scanf("%d",&x);
        addedge(0,i,1,0);
        addedge(0,i+n,1,x);
        addedge(i+n,n*2+1,1,0);
    }
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&ch);
        if (x>y)swap(x,y);
        addedge(x,y+n,1,ch);
    }
    while (spfa());
    printf("%d\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000000;
int n,m,p,i,j,k,x,y,ch,edgenum,ans;
int a[300][300],head[M],vet[M],next[M],flag[M],len[M],size[M],h[M*30],dis[1010],pre[M][2],rem[M];
void addedge(int x,int y,int z,int w){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=z;
    len[edgenum]=w;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=0;
    len[edgenum]=-w;
}
int spfa(){
    int l=1,r=1;
    for (i=0;i<=n*2+1;i++)dis[i]=inf;
    dis[0]=0;h[1]=0;flag[0]=1;rem[0]=inf;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]>dis[u]+len[e]){
                dis[v]=dis[u]+len[e];
                pre[v][0]=u;pre[v][1]=e;
                rem[v]=min(rem[u],size[e]);
                if (!flag[v]){
                    flag[v]=1;
                    h[++r]=v;
                }
            }
        }
        l++;
        flag[u]=0;
    }
    if (dis[2*n+1]==inf)return 0;
    ans+=rem[2*n+1]*dis[2*n+1];
    int u=2*n+1;
    while (u){
        size[pre[u][1]]-=rem[2*n+1];
        size[pre[u][1]^1]+=rem[2*n+1];
        u=pre[u][0];
    }
    return 1;
}
int main(){
    edgenum=1;
    //freopen("1.out","w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    n++;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            a[i][j]=inf;
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&ch);
        x++;y++;
        a[x][y]=min(a[x][y],ch);
        a[y][x]=min(a[y][x],ch);
    }
    for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
            for (j=k;j<=n;j++)
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
    addedge(0,1,p,0);
    for (i=2;i<=n;i++){
        addedge(0,i,1,0);
        addedge(i+n,n*2+1,1,0);
    }
    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
            if (a[i][j]!=inf)addedge(i,j+n,1,a[i][j]);
    while (spfa());
    printf("%d\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=500010;
const int inf=1000000007;
int n,m,i,x,y,ch,ans,edgenum;
int a[M],head[M],vet[M],next[M],flag[M],size[M],len[M],dis[M],h[M],rem[M],pre[M][2];
void addedge(int x,int y,int z,int w){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=z;
    len[edgenum]=w;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=0;
    len[edgenum]=-w;
}
int spfa(){
    int l=1,r=1;
    for (i=0;i<=n+2;i++)dis[i]=inf;
    h[1]=0;dis[0]=0;rem[0]=inf;flag[0]=1;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]>dis[u]+len[e]){
                dis[v]=dis[u]+len[e];
                pre[v][0]=u;pre[v][1]=e;
                rem[v]=min(rem[u],size[e]);
                if (!flag[v]){
                    flag[v]=1;
                    h[++r]=v;
                }
            }
        }
        l++;
        flag[u]=0;
    }
    if (dis[n+2]==inf)return 0;
    ans+=dis[n+2]*rem[n+2];
    int u=n+2;
    while (u){
        size[pre[u][1]]-=rem[n+2];
        size[pre[u][1]^1]+=rem[n+2];
        u=pre[u][0];
    }
    return 1;
}
int main(){
    edgenum=1;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        scanf("%d",&a[i]);
        addedge(i+1,i,inf,0);
    }
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&ch);
        addedge(x,y+1,inf,ch);
    }
    for (i=1;i<=n+1;i++){
        int x=a[i]-a[i-1];
        if (x>0)addedge(0,i,x,0);
            else addedge(i,n+2,-x,0);
    }
    while (spfa());
    printf("%d\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000007;
int n,m,i,j,cnt,edgenum,ans;
int a[110][110],head[M],vet[M],next[M],len[M],size[M],flag[M],rem[M],dis[M],h[M<<3],pre[M][2],orz[M],num[M];
void addedge(int x,int y,int z,int w){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=z;
    len[edgenum]=w;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=0;
    len[edgenum]=-w;
}
int spfa(){
    int l=1,r=1;
    for (int i=0;i<=cnt;i++)dis[i]=inf;
    dis[0]=0;flag[0]=1;rem[0]=inf;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]>dis[u]+len[e]){
                dis[v]=dis[u]+len[e];
                pre[v][0]=u;pre[v][1]=e;
                rem[v]=min(rem[u],size[e]);
                if (!flag[v]){
                    flag[v]=1;
                    h[++r]=v;
                }
            }
        }
        /*printf("%d:",u);
        for (int i=0;i<=cnt;i++)printf("%d ",dis[i]);
        puts("");*/
        l++;
        flag[u]=0;
    }
    if (dis[n+m+1]==inf)return 0;
    ans+=dis[n+m+1]*rem[n+m+1];
    int u=n+m+1;
    while (u){
        size[pre[u][1]]-=rem[n+m+1];
        size[pre[u][1]^1]+=rem[n+m+1];      
        if (!pre[u][0]){
            orz[++cnt]=orz[u]+1,num[cnt]=num[u];
            addedge(0,cnt,1,0);
            for (int i=1;i<=m;i++)
                addedge(cnt,n+i,1,a[num[cnt]][i]*orz[cnt]);
        }
        u=pre[u][0];
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    edgenum=1,cnt=n+m+1;
    for (j=1;j<=m;j++)
        for (i=1;i<=n;i++)scanf("%d",&a[i][j]);
    for (i=1;i<=n;i++){
        orz[i]=1,num[i]=i;
        addedge(0,i,1,0);
        for (j=1;j<=m;j++)addedge(i,j+n,1,a[i][j]);
    }
    for (i=1;i<=m;i++)addedge(n+i,n+m+1,1,0);
    while (spfa());
    printf("%.2lf\n",(double)ans/m);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000007;
int head[M*30],vet[M*30],next[M*30],size[M*30],len[M*30],dis[M],flag[M],rem[M],pre[M][2],a[110][110],h[M*30],orz[M],num[M];
int n,m,i,j,x,edgenum,ans,cnt;
void addedge(int x,int y,int z,int w){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=z;
    len[edgenum]=w;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=0;
    len[edgenum]=-w;
}
int spfa(){
    int l=1,r=1;
    for (int i=0;i<=cnt;i++)dis[i]=inf;
    dis[0]=0;flag[0]=1;rem[0]=inf;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]>dis[u]+len[e]){
                dis[v]=dis[u]+len[e];
                pre[v][0]=u;pre[v][1]=e;
                rem[v]=min(rem[u],size[e]);
                if (!flag[v]){
                    flag[v]=1;
                    h[++r]=v;
                }
            }
        }
        l++;
        flag[u]=0;
    }
    if (dis[n+m+1]==inf)return 0;
    ans+=dis[n+m+1]*rem[n+m+1];
    int u=n+m+1;
    while (u){
        size[pre[u][1]]-=rem[n+m+1];
        size[pre[u][1]^1]+=rem[n+m+1];
        if (!pre[u][0]){
            orz[++cnt]=orz[u]+1,num[cnt]=num[u];
            addedge(0,cnt,1,0);
            for (int i=1;i<=m;i++)addedge(cnt,i+n,1,a[num[cnt]][i]*orz[cnt]);
        }
        u=pre[u][0];
    }
    return 1;
}
int main(){
    scanf("%d%d",&m,&n);
    edgenum=1;cnt=n+m+1;
    for (i=1;i<=m;i++){
        scanf("%d",&x);
        addedge(i+n,n+m+1,x,0);
    }
    for (j=1;j<=m;j++)
        for (i=1;i<=n;i++)scanf("%d",&a[i][j]);
    for (i=1;i<=n;i++){
        addedge(0,i,1,0);
        orz[i]=1;num[i]=i;
        for (j=1;j<=m;j++)addedge(i,j+n,1,a[i][j]);
    }
    while (spfa());
    printf("%d\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=400010;
const int inf=1000000007;
int n,m,i,edgenum,tmp,S,T,len,ans;
int head[M],vet[M],next[M],size[M],h[M],dis[M];
struct shit{int st,ed,len;}a[M];
bool cmp(shit x,shit y){return x.len<y.len;}
void addedge(int x,int y){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=1;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=1;
}
int bfs(){
    int l=1,r=1;
    memset(dis,-1,sizeof dis);
    h[1]=S;dis[S]=0;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]<0){
                dis[v]=dis[u]+1;
                h[++r]=v;
            }
        }
        l++;
    }
    if (dis[T]<0)return 0;else return 1;
}
int dfs(int u,int aug){
    if (u==T)return aug;
    int flow=0;
    for (int e=head[u];e;e=next[e]){
        int v=vet[e];
        if (size[e]&&dis[v]==dis[u]+1){
            int tmp=dfs(v,min(aug-flow,size[e]));
            flow+=tmp;
            size[e]-=tmp;
            size[e^1]+=tmp;
            if (flow==aug)return flow;
        }
    }
    if (!flow)dis[u]=-1;
    return flow;
}
int main(){
    edgenum=1;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)scanf("%d%d%d",&a[i].st,&a[i].ed,&a[i].len);
    sort(a+1,a+m+1,cmp);
    scanf("%d%d%d",&S,&T,&len);
    for (i=1;i<=m;i++)
        if (a[i].len<len)addedge(a[i].st,a[i].ed);
            else break;
    while (bfs())ans+=dfs(S,inf);
    memset(head,0,sizeof head);
    memset(size,0,sizeof size);
    edgenum=1;
    for (i=m;i;i--)
        if (a[i].len>len)addedge(a[i].st,a[i].ed);
            else break;
    while (bfs())ans+=dfs(S,inf);
    printf("%d\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000007;
int n,m,i,j,k,edgenum,x,ans;
int u[2]={0,1},v[2]={1,0};
int head[M],vet[M],next[M],size[M],dis[M],h[M];
int point(int x,int y){return (x-1)*m+y;}
void addedge(int x,int y,int ch){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=ch;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=ch;
}
int bfs(){
    int l=1,r=1;
    memset(dis,-1,sizeof dis);
    dis[0]=1;h[1]=0;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]<0){
                dis[v]=dis[u]+1;
                h[++r]=v;
            }
        }
        l++;
    }
    if (dis[n*m+1]<0)return 0;else return 1;
}
int dfs(int u,int aug){
    if (u==n*m+1)return aug;
    int flow=0;
    for (int e=head[u];e;e=next[e]){
        int v=vet[e];
        if (size[e]&&dis[v]==dis[u]+1){
            int tmp=dfs(v,min(aug-flow,size[e]));
            flow+=tmp;
            size[e]-=tmp;
            size[e^1]+=tmp;
            if (flow==aug)return flow;
        }
    }
    if (!flow)dis[u]=-1;
    return flow;
}
int main(){
    edgenum=1;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            for (k=0;k<2;k++){
                int x=i+u[k],y=j+v[k];
                if (x<=n&&y<=m)addedge(point(i,j),point(x,y),1);
            }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            scanf("%d",&x);
            if (x==1)addedge(0,point(i,j),inf);else if (x==2)addedge(point(i,j),n*m+1,inf);
        }
    while (bfs())ans+=dfs(0,inf);
    printf("%d\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=500010;
const int inf=1000000007;
int head[M],vet[M],next[M],size[M],h[M],dis[M>>3];
int n,m,i,x,y,ch,ans,edgenum;
void addedge(int x,int y,int ch){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=ch;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=0;
}
int bfs(){
    int l=1,r=1;
    memset(dis,-1,sizeof dis);
    dis[0]=1;h[1]=0;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]<0){
                dis[v]=dis[u]+1;
                h[++r]=v;
            }
        }
        l++;
    }
    if (dis[n+m+1]<0)return 0;else return 1;
}
int dfs(int u,int aug){
    if (u==n+m+1)return aug;
    int flow=0;
    for (int e=head[u];e;e=next[e]){
        int v=vet[e];
        if (size[e]&&dis[v]==dis[u]+1){
            int tmp=dfs(v,min(aug-flow,size[e]));
            flow+=tmp;
            size[e]-=tmp;
            size[e^1]+=tmp;
            if (flow==aug)return flow;
        }
    }
    if (!flow)dis[u]=-1;
    return flow;
}
int main(){
    edgenum=1;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        scanf("%d",&x);
        addedge(0,i,x);
    }
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&ch);
        addedge(x,n+i,inf);
        addedge(y,n+i,inf);
        addedge(n+i,n+m+1,ch);
        ans+=ch;
    }
    while (bfs())ans-=dfs(0,inf);
    printf("%d\n",ans);
}