源点向起点连边，终点向汇点连边。
点点之间连边，一条是流量无限不花钱的，一条是流量为1花钱的
最大费用最大流即可。
By：大奕哥
1 #include2 using namespace std; 3 const int N=25005,inf=1e9; 4 int d[N],head[N],cnt=-1,a,b,P,Q,num,p[105][105],cost,f[N],s,t; 5 bool v[N]; 6 struct node{ 7 int w,to,nex,c,f; 8 }e[1000005]; 9 void add(int x,int y,int w,int c)10 {11 e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;e[cnt].f=x;e[cnt].w=w;e[cnt].c=c;12 e[++cnt].to=x;e[cnt].nex=head[y];head[y]=cnt;e[cnt].f=y;e[cnt].w=0;e[cnt].c=-c;13 }14 queue q;15 bool spfa()16 {17 memset(d,0x3f,sizeof(d));18 memset(v,0,sizeof(v));19 memset(f,-1,sizeof(f));20 v[s]=1;d[s]=0;q.push(s);21 while(!q.empty())22 {23 int x=q.front();q.pop();v[x]=0;24 for(int i=head[x];i!=-1;i=e[i].nex)25 {26 if(!e[i].w||d[e[i].to]<=d[x]+e[i].c)continue;27 int y=e[i].to;28 d[y]=d[x]+e[i].c;f[y]=i;29 if(!v[y])30 {31 q.push(y);v[y]=1;32 }33 }34 }35 if(d[t]>inf)return 0;36 int flow=inf;37 for(int i=f[t];i!=-1;i=f[e[i].f])38 flow=min(flow,e[i].w);39 for(int i=f[t];i!=-1;i=f[e[i].f])40 e[i].w-=flow,e[i^1].w+=flow,cost+=flow*e[i].c;41 return 1;42 }43 int main()44 {45 scanf("%d%d",&a,&b);46 scanf("%d%d",&P,&Q);47 memset(head,-1,sizeof(head));48 for(int i=0;i<=P;++i)49 for(int j=0;j<=Q;++j)50 p[i][j]=++num;51 s=0;t=num+1;int x,k,y;52 for(int i=0;i<=P;++i)53 for(int j=1;j<=Q;++j)54 {55 scanf("%d",&x);56 add(p[i][j-1],p[i][j],1,-x);57 add(p[i][j-1],p[i][j],inf,0);58 }59 for(int j=0;j<=Q;++j)60 for(int i=1;i<=P;++i)61 {62 scanf("%d",&x);63 add(p[i-1][j],p[i][j],1,-x);64 add(p[i-1][j],p[i][j],inf,0);65 }66 for(int i=1;i<=a;++i)67 {68 scanf("%d%d%d",&k,&x,&y);69 add(s,p[x][y],k,0);70 }71 for(int i=1;i<=b;++i)72 {73 scanf("%d%d%d",&k,&x,&y);74 add(p[x][y],t,k,0);75 }76 while(spfa());77 printf("%d\n",-cost);78 return 0;79 }