1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
const int N = 2000 + 100, INF = 1E9, inf = 5000;
struct E {
int from, to, cp, v;
E() {}
E(int f, int t, int cp, int v) : from(f), to(t), cp(cp), v(v) {}
};
struct MCMF {
int n, m, s, t;
vector<E> edges;
vector<int> G[N];
bool inq[N];
int d[N];
int p[N];
int a[N];
void init(int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
FOR (i, 0, n + 1) G[i].clear();
edges.clear(); m = 0;
}
void addedge(int from, int to, int cap, int cost) {
edges.emplace_back(from, to, cap, cost);
edges.emplace_back(to, from, 0, -cost);
G[from].push_back(m++);
G[to].push_back(m++);
}
bool BellmanFord(int &flow, int &cost) {
FOR (i, 0, n + 1) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int& idx: G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF) return false;
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
return true;
}
int go() {
int flow = 0, cost = 0;
while (BellmanFord(flow, cost));
dbg(flow);
return cost;
}
} MM;
vector<pair<int, int>> V;
int n, m, k, t;
bool check(int c) {
MM.init(n + 1, n, n - 1);
MM.addedge(n, 0, k, 0);
for (auto& x: V) {
MM.addedge(x.first, x.second, c + 1, 0);
MM.addedge(x.second, x.first, c + 1, 0);
MM.addedge(x.first, x.second, inf, 1);
MM.addedge(x.second, x.first, inf, 1);
}
int cost = MM.go();
dbg(c, cost);
return cost <= t;
}
int main() {
cin >> n >> m >> k >> t;
FOR (_, 0, m) {
int u, v; scanf("%d%d", &u, &v);
V.emplace_back(u, v);
}
int l = 0, r = k, ans = -1;
while (l <= r) {
int m = (l + r) / 2;
if (check(m)) { r = m - 1; ans = m; }
else l = m + 1;
}
cout << ans << endl;
}
|