记录编号	86652	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 深海机器人	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-01-27 11:58:54	内存使用	0.29 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
using namespace std;
const int SIZEN=1000,INF=0x7fffffff/2;
class EDGE{
public:
	int from,to,cap,flow,cost;
};
vector<EDGE> edges;
vector<int> c[SIZEN];//邻接表
int N;//范围是从0到N
void addedge(int from,int to,int cap,int cost){
	edges.push_back((EDGE){from,to,cap,0,cost});
	edges.push_back((EDGE){to,from,0,0,-cost});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
int anscost=0;
bool SPFA(int S,int T){
	queue<int> Q;
	bool inq[SIZEN]={0};
	int f[SIZEN]={0};
	int father[SIZEN]={0};
	int i,x;
	for(i=0;i<=N;i++) f[i]=-INF;
	f[S]=0,inq[S]=true,Q.push(S);
	while(!Q.empty()){
		x=Q.front();inq[x]=false;Q.pop();
		for(i=0;i<c[x].size();i++){
			EDGE& e=edges[c[x][i]];
			if(e.cap<=e.flow) continue;
			if(f[x]+e.cost>f[e.to]){
				f[e.to]=f[x]+e.cost;
				father[e.to]=c[x][i];
				if(!inq[e.to]){
					inq[e.to]=true;
					Q.push(e.to);
				}
			}
		}
	}
	if(f[T]==-INF) return false;
	int minf=INF;
	x=T;
	while(x!=S){
		EDGE& e=edges[father[x]];
		minf=min(minf,e.cap-e.flow);
		x=e.from;
	}
	anscost+=minf*f[T];
	x=T;
	int now;
	while(x!=S){
		now=father[x];
		edges[now].flow+=minf;
		edges[now^1].flow-=minf;
		x=edges[now].from;
	}
	return true;
}
void MCMF(int S,int T){
	while(SPFA(S,T));
	printf("%d\n",anscost);
}
//下标从0开始
int S,T;
int A,B;//出发位置数,目的地数
const int SIZEP=51;
int P,Q;//意义同题
int hash(int x,int y){
	return x*(P+1)+y;
}
void init(void){
	scanf("%d%d%d%d",&A,&B,&P,&Q);
	for(int i=0;i<=P;i++){
		for(int j=0;j<Q;j++){
			//向东,从(j,i)移向(j+1,i)
			int val;scanf("%d",&val);
			addedge(hash(j,i),hash(j+1,i),1,val);
			addedge(hash(j,i),hash(j+1,i),INF,0);
		}
	}
	for(int i=0;i<=Q;i++){
		for(int j=0;j<P;j++){
			//向北,从(i,j)移向(i,j+1)
			int val;scanf("%d",&val);
			addedge(hash(i,j),hash(i,j+1),1,val);
			addedge(hash(i,j),hash(i,j+1),INF,0);
		}
	}
	N=hash(Q,P);//现在0~N是格点的编号,令N+1为源,N+2为汇
	S=N+1,T=N+2;
	//注意,本题中出发地和目的地的坐标和题干里是反着来的,例如题干里的(Q,P)在输入文件中就是(P,Q)
	for(int i=1;i<=A;i++){
		int k,x,y;scanf("%d%d%d",&k,&y,&x);//k个可从(x,y)出发
		addedge(S,hash(x,y),k,0);//源点向出发点连边
	}
	for(int i=1;i<=B;i++){
		int r,x,y;scanf("%d%d%d",&r,&y,&x);//r个可从(x,y)到达
		addedge(hash(x,y),T,r,0);//目的地向汇点连边
	}
	N+=2;//修改N的值,因为加上了源点和汇点
}
int main(){
	freopen("shinkai.in","r",stdin);
	freopen("shinkai.out","w",stdout);
	init();
	MCMF(S,T);
	return 0;
}