提交记录

感觉非常迷惑

比较正经的Dinic，调了很久找不出问题

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
#define rint register int
#define lint long long
using namespace std;
inline int read(){
	char c;int f=1,res=0;
	while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
	while(isdigit(c))res=res*10+c-'0',c=getchar();
	return f*res;
}
const int P=85,N=2e4+5,M=6e5+5;
const double INF=1e15,eps=1e-10;
int hed[N],ver[M],nxt[M],cnt=1;
double f[M];
inline void inst(int u,int v,double _f){
	if(u<=0||v<=0)return;
//	cerr<<"inst:"<<u<<" "<<v<<" "<<_f<<endl;
	ver[++cnt]=v;
	nxt[cnt]=hed[u];
	hed[u]=cnt;
	f[cnt]=_f;
	ver[++cnt]=u;
	nxt[cnt]=hed[v];
	hed[v]=cnt;
	f[cnt]=0;
}
int n,m,p,y,T,s,t;
double w[P][P],c[P],ans;
inline int id(int x,int y){//µÚxλѡÊÖµÚyÌ×Ìâ¶ÔÓ¦µÄµã±àºÅ
	if(y<1||y>m+1)return 0;
//	cout<<"id:"<<x<<" "<<y<<endl;
	return (x-1)*(m+1)+y;
}
inline void init(){
	cnt=1;
	memset(hed,0,sizeof hed);
	memset(w,0,sizeof w);
}
int dep[N];
inline bool BFS(){
	memset(dep,0,sizeof dep);
	queue<int> que;
	dep[s]=1;
	que.push(s);
	while(!que.empty()){
		int u=que.front();
		que.pop();
		for(rint i=hed[u];i;i=nxt[i]){
			int v=ver[i];
			if(dep[v]||f[i]<=eps)continue;
			dep[v]=dep[u]+1;
//			cerr<<"BFS:"<<u<<" "<<v<<endl;
			if(v==t)return true;
			que.push(v);
		}
	}
	return false;
}
double DFS(int u,double incf){
//	cerr<<"DFS:"<<u<<" "<<incf<<endl;
	if(u==t||incf<=eps)return incf;
	double out=0;
	for(rint i=hed[u];i;i=nxt[i]){
		int v=ver[i];
		if(f[i]<=eps||dep[v]!=dep[u]+1)continue;
		double upd=DFS(v,min(incf,f[i]));
		out+=upd;
		incf-=upd;
		f[i]-=upd;
		f[i^1]+=upd;
		if(incf<=eps)break;
	}
	return out;
}
inline double Dinic(){
	double res=0;
	while(BFS()){
//		cerr<<"BFS Finished."<<endl;
//		for(rint i=1;i<=t;++i)
//			cerr<<"dep:"<<i<<" "<<dep[i]<<endl;
		res+=DFS(s,INF);
		if(res>=INF)return res;
//		cerr<<"res:"<<res<<endl;
	}
	return res;
}
int main(){
	T=read();
	while(T--){
		init();
		n=read();
		m=read();
		p=read();
		y=read();
		for(rint i=1;i<=p;++i)
			scanf("%lf",&c[i]);
		for(rint j=1;j<=m;++j)
			for(rint i=1;i<=n;++i){
				double pre=1,sum=0;
				for(rint k=1;k<=p;++k){
					double a;
					scanf("%lf",&a);
					w[i][j]+=pre*(1.0-a)*sum;
					pre*=a;
					sum+=c[k];
				}
				w[i][j]+=pre*sum;
//				cerr<<"w:"<<i<<" "<<j<<" "<<w[i][j]<<endl;
			}
		s=N-2;t=N-1;
//		cerr<<"s:"<<s<<" t:"<<t<<endl;
		for(rint i=1;i<=n;++i){
			for(rint j=1;j<=m;++j){
				inst(id(i,j),id(i,j+1),w[i][j]);
				inst(id(i,j+1),id(i,j),INF);
			}
			inst(s,id(i,1),INF);
			inst(id(i,m+1),t,INF); 
		}
		for(rint i=1;i<=y;++i){
			int a,b,c;
			a=read();
			b=read();
			c=read();
			for(rint j=1;j<=m;++j)
				inst(id(b,j),id(a,j+c),INF);
		}
		ans=Dinic();
		if(ans>=INF)printf("-1\n");
		else printf("%lf\n",ans);
	}
	return 0;
}