BZOJ 5070 危险的迷宫

题目大意

给你一个N*M的网格图，每个网格点都有一个权值，每个网格点只能通过一个人，一些网格点之间有边连接。给你K个起点和K的终点（不重），求K个人从起点到终点的最小权值和。

费用流裸题。

好久没写费用流都忘了……每次从S进行一次到T的SPFA()最短路，最短路更新条件是$dis_{to[i]} > dis_{tmp} + cost_i$，求得最短路之后回溯更新，求出花费和流量。

数组开小了，我调试了1h左右以为保留字被覆盖了= =只见这数组动都没动过了一会被碾压得啥也不剩腥风血雨qwq

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define GA(x,y) (x-1)*m+y
#define GB(x,y) n*m+(x-1)*m+y
#define INF 1<<30
#define N 20
#define M 1000010
int n,m,k,v[N][N],S,T,ix,ia,ib,ic,id,ans,res;
int from[(N*N)<<1],pre[(N*N)<<1],dis[(N*N)<<1];
int to[M],nex[M],val[M],prc[M],head[(N*N)<<1],tot=1;
queue<int>q;
inline void AE(int tx,int ty,int ta,int tb)
{
    to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=ta,prc[tot]=tb;
    to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot,val[tot]=0,prc[tot]=-tb;
}
inline bool spfa()
{
    q.push(S);
    memset(dis,0x3f,sizeof dis);
    dis[S]=0;
    from[T]=-1;
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        for(int i=head[tmp];i;i=nex[i]) if(val[i]&&dis[to[i]]>dis[tmp]+prc[i])
        {
            dis[to[i]]=dis[tmp]+prc[i];
            from[to[i]]=tmp;
            pre[to[i]]=i;
            q.push(to[i]);
        }
    }
    return ~from[T];
}
inline void calc()
{
    int ret=0x3f3f3f3f;
    for(int i=T;i!=S;i=from[i])
        ret=min(ret,val[pre[i]]);
    for(int i=T;i!=S;i=from[i]) val[pre[i]]-=ret,val[pre[i]^1]+=ret,res+=prc[pre[i]]*ret;
    ans+=ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    S=0,T=((n*m)<<1)+1;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&ix),AE(GA(i,j),GB(i,j),1,ix);
    scanf("%d",&k);
    while(k--)
        scanf("%d%d%d%d",&ia,&ib,&ic,&id),AE(GB(ia,ib),GA(ic,id),1,0),AE(GB(ic,id),GA(ia,ib),1,0);
    scanf("%d",&k);
    for(int i=1;i<=k;++i) scanf("%d%d",&ia,&ib),AE(S,GA(ia,ib),1,0);
    for(int i=1;i<=k;++i) scanf("%d%d",&ia,&ib),AE(GB(ia,ib),T,1,0);
    while(spfa()) calc();
    if(ans!=k) printf("-1\n");
    else printf("%d\n",res);
    return 0;
}