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

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 155;
const int MAXM = 205;
const int MAXT = 155;

int n, m, w, t;
int eu[MAXM], ev[MAXM], v[MAXN][MAXT];

namespace Dinic {
	const int MAXV = MAXN*MAXT;
	const int MAXE = MAXV + MAXM*2*MAXT;

	struct Edge {
		int u, v, c, f;
		Edge(){}
		Edge( int u, int v, int c, int f ):
			u(u),v(v),c(c),f(f){}
	};
	int n, s, t;
	Edge edge[MAXE<<1];
	int head[MAXV], nxt[MAXE<<1], eidx = 0;
    void init( int n2, int s2, int t2 ) {
		n = n2, s = s2, t = t2;
		eidx = 0;
		memset(head, -1, sizeof(head));
	}
	void adde( int u, int v, int c ) {
		edge[eidx] = Edge(u,v,c,0);
		nxt[eidx] = head[u], head[u] = eidx++;
		edge[eidx] = Edge(v,u,0,0);
		nxt[eidx] = head[v], head[v] = eidx++;
	}

	int cur[MAXV], dis[MAXV];
	queue<int> q;
	bool bfs() {
		memset(dis, 0x3f, sizeof(dis));
		dis[s] = 0, q.push(s);
		while( !q.empty() ) {
			int u = q.front(); q.pop();
			for( int i = head[u]; ~i; i = nxt[i] ) {
				Edge &e = edge[i];
				if( e.c > e.f && dis[u] + 1 < dis[e.v] ) {
					dis[e.v] = dis[u] + 1;
					q.push(e.v);
				}
			}
		}
		return dis[t] != INF;
	}
	int dfs( int u, int res ) {
		if( u == t || res == 0 ) return res;
		int flow = 0;
		for( int &i = cur[u]; ~i; i = nxt[i] ) {
			Edge &e = edge[i];
			if( e.c > e.f && dis[e.v] == dis[u] + 1 ) {
				int f = dfs(e.v, min(res, e.c-e.f));
				flow += f;
				res -= f;
				e.f += f;
				edge[i^1].f -= f;
				if( !res ) break;
			}
		}
		return flow;
	}
	ll solve() {
		ll flow = 0;
		while( bfs() ) {
			for( int i = 0; i < n; ++i ) cur[i] = head[i];
			flow += dfs(s,INF);
		}
		return flow;
	}
}

int id( int i, int j ) {
	return (i-1)*(t+1) + j;
}
bool check( int c ) {
	int S = n*(t+1), T = S+1;
	Dinic::init(T+1, S, T);
	for( int i = 1; i <= n; ++i ) {
		Dinic::adde(S, id(i,0), INF);
		for( int j = 1; j <= t; ++j )
			Dinic::adde(id(i,j-1), id(i,j), v[i][j]);
		Dinic::adde(id(i,t), T, INF);
	}
	for( int e = 0; e < m; ++e ) {
		int a = eu[e], b = ev[e];
		for( int i = c; i <= t; ++i ) {
			Dinic::adde(id(a,i), id(b,i-c), INF);
			Dinic::adde(id(b,i), id(a,i-c), INF);
		}
	}
	return Dinic::solve() <= w;
}

void solve() {
	int low = 0, high = t;
	while( low < high ) {
		int mid = (low + high)/2;
		if( check(mid) ) high = mid;
		else low = mid+1;
	}
	printf( "%d\n", low == t ? -1 : low );
}

int main() {
	freopen( "cdcq_c.in", "r", stdin );
	freopen( "cdcq_c.out", "w", stdout );
	scanf( "%d%d%d%d", &n, &m, &w, &t );
	for( int i = 0; i < m; ++i ) scanf( "%d%d", eu+i, ev+i );
	for( int i = 1; i <= n; ++i )
		for( int j = 1; j <= t; ++j )
			scanf( "%d", &v[i][j] );
	solve();
	return 0;
}