记录编号	394052	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	源符「厌川的翡翠」	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	13.959 s
提交时间	2017-04-12 20:34:31	内存使用	18.13 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int INF=1e9+7;

inline int min(int a,int b){return a<b?a:b;}
int n,m,w,t,g[160][160],v[160][160];

struct SAP{
	int head[100010],to[1000010],next[1000010],f[1000010],c[1000010],pre[100010];
	int tot,cnt,s,T,dis[100010],Q[100010],num[100010],cur[100010],qhead,tail;
	inline void ae(int &u,int &v,int w,int x){
		++tot; to[tot]=v; c[tot]=w; f[tot]=x;
		next[tot]=head[u]; head[u]=tot;
	}
	inline void AE(int u,int v,int w,int x){
		ae(u,v,w,x); ae(v,u,0,0);
	}
	inline void bfs(){
		Q[tail++]=T;
		while(qhead<tail){
			int u=Q[qhead++];
			for(int p=head[u];p;p=next[p])
				if(!dis[to[p]]&&to[p]!=T)
					dis[to[p]]=dis[u]+1,Q[tail++]=to[p];
		}
	}
	inline int ar(){
		int flow=INF;
		for(int x=T;x!=s;x=to[pre[x]^1])
			flow=min(flow,c[pre[x]]-f[pre[x]]);
		for(int x=T;x!=s;x=to[pre[x]^1])
			f[pre[x]]+=flow,f[pre[x]^1]-=flow;
		return flow;
	}
	int maxflow(){
		bfs();
		for(int i=1;i<=cnt;i++) cur[i]=head[i];
		for(int i=1;i<=cnt;i++) num[dis[i]]++;
		int x=s,ok,ans=0;
		while(dis[s]<cnt){
			if(x==T) ans+=ar(),x=s;
			ok=false;
			for(int p=cur[x];p;p=next[p])
				if(dis[to[p]]+1==dis[x]&&c[p]>f[p]){
					pre[to[p]]=p;
					ok=true;
					cur[x]=p;
					x=to[p];
					break;
				}
			if(!ok){
				int mn=cnt;
				for(int p=head[x];p;p=next[p])
					if(c[p]>f[p])
						mn=min(mn,dis[to[p]]);
				if(--num[dis[x]]==0) break;
				num[dis[x]=mn+1]++; cur[x]=head[x];
				if(x!=s) x=to[pre[x]^1];
			}
		}
		return ans;
	}
	int id[160][160];
	void start(){
		cnt=2;
		for(int i=1;i<=n;i++)
			for(int j=0;j<=t;j++)
				id[i][j]=++cnt;
		 s=1; T=2;
	}
	void reset(int c){
		for(int i=1;i<=cnt;i++) dis[i]=head[i]=0;
		tot=1; qhead=tail=0;
		for(int i=1;i<=n;i++){
			AE(s,id[i][0],INF,0); AE(id[i][t],T,INF,0);
			for(int j=0;j<t;j++)
				AE(id[i][j],id[i][j+1],v[i][j+1],0);
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(g[i][j]){
					for(int k=1;k<=t;k++){
						AE(id[i][k],k>c?id[j][k-c]:id[j][0],INF,0);
					}
				}
	}
}sap;

int main(){
	//freopen("a.txt","r",stdin);
	freopen("cdcq_c.in","r",stdin);
	freopen("cdcq_c.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&w,&t);
	for(int i=1;i<=m;i++){
		int x,y; scanf("%d%d",&x,&y);
		g[x][y]=g[y][x]=true;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=t;j++)
			scanf("%d",&v[i][j]);
	sap.start();
	int l=0,r=t,ans=-1;
	while(l<=r){
		int mid=(l+r)>>1; sap.reset(mid);
		if(sap.maxflow()<=w) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}