#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <iostream> using namespace std; const int maxn = 4010; const int INF = 1e9+10; struct Edge{ int to, cap, rev; }; vector<Edge> G[maxn]; int cnt[maxn]; int level[maxn]; int s, t; int n, m, k; int l, r; void add_edge(int u, int v, int cap){ G[u].push_back(Edge{v, cap, G[v].size()}); G[v].push_back(Edge{u, 0, G[u].size()-1}); } void bfs(int s){ memset(level, -1, sizeof(level)); queue<int> q; q.push(s); level[s] = 0; while(!q.empty()){ int v = q.front(); q.pop(); for(int i=0; i<G[v].size(); i++){ Edge& e = G[v][i]; if(e.cap>0&&level[e.to]<0){ level[e.to] = level[v]+1; q.push(e.to); } } } } int dfs(int v, int t, int flow){ if(v == t) return flow; for(int& i=cnt[v]; i<G[v].size(); i++){ Edge& e = G[v][i]; if(e.cap>0&&level[v]<level[e.to]){ int d = dfs(e.to, t, min(flow, e.cap)); if(d>0){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t){ int flow = 0; for(;;){ bfs(s); if(level[t]<0) return flow; int f; memset(cnt, 0, sizeof(cnt)); while((f = dfs(s, t, INF))>0){ flow+=f; } } } int d[maxn]; int main() { int kase = 1; while(~scanf("%d%d%d", &n, &m, &k)){ for(int i=0; i<maxn; i++) G[i].clear(); memset(d, 0, sizeof(d)); scanf("%d%d", &l, &r); int u, v; int sum = 0; for(int i=0; i<k; i++){ scanf("%d %d", &u, &v); add_edge(u, v+n, 1); } int ss = 4002; int tt = 4003; for(int i=1; i<=n; i++) add_edge(0, i, r-l), add_edge(ss, i, l); for(int i=1; i<=m; i++) add_edge(i+n, 4001, r-l), add_edge(i+n, tt, l); add_edge(4001, 0, 1000000); int ans = max_flow(ss, tt); if(ans == n*l)printf("Case %d: Yes\n", kase++); else printf("Case %d: No\n", kase++); } return 0; }
|