Problem 2232 炉石传说

Problem 2232 炉石传说

不知道fzu的账号在哪里弄，想要做题的可以到vj上面去做 https://vjudge.net/problem/FZU-2232

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

#include <cstring>

using namespace std;

const int maxn = , inf = 0x3f3f3f;

struct Edge {

    int from, to, cap, flow;

};

struct Dinic {

    int n, m, s, t;

    vector<Edge> edges;

    vector<int> G[maxn];

    bool vis[maxn];

    int d[maxn];

    int cur[maxn];

    void init(int n) {

        this->n = n;

        for (int i = ; i <= n; ++i) {

            G[i].clear();

        }

        edges.clear();

    }

    void AddEdge(int from, int to, int cap) {

        edges.push_back((Edge){from, to, cap, });

        edges.push_back((Edge){to, from, , });

        m = edges.size();

        G[from].push_back(m-);

        G[to].push_back(m-);

    }

    bool bfs() {

        memset(vis, , sizeof(vis));

        queue<int> que;

        que.push(s);

        d[s] = ;

        vis[s] = true;

        while (!que.empty()) {

            int x = que.front(); que.pop();

            for (int i = ; i < G[x].size(); ++i) {

                Edge& e = edges[G[x][i]];

                if (!vis[e.to] && e.cap > e.flow) {

                    vis[e.to] = true;

                    d[e.to] = d[x] + ;

                    que.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int dfs(int x, int a) {

        if (x == t || a == ) return a;

        int flow = , f;

        for (int& i = cur[x]; i < G[x].size(); ++i) {

            Edge& e = edges[G[x][i]];

            if (d[x] +  == d[e.to] && (f = dfs(e.to, min(a, e.cap-e.flow))) > ) {

                e.flow += f;

                edges[G[x][i]^].flow -= f;

                flow += f;

                a -= f;

                if (a == ) break;

            }

        }

        return flow;

    }

    int maxflow(int s, int t) {

        this->s = s; this->t = t;

        int flow = ;

        while (bfs()) {

            memset(cur,,sizeof(cur));

            flow += dfs(s,inf);

        }

        return flow;

    }

}dinic;

int a[maxn], b[maxn], c[maxn], d[maxn];

int main() {

    int T; scanf("%d",&T);

    while (T--) {

        int n; scanf("%d",&n);

        int s = n+n+, t = n+n+;

        dinic.init(n*+);

        for (int i = ; i <= n; ++i) {

            scanf("%d%d",&a[i],&b[i]);

            dinic.AddEdge(s,i,);

        }

        for (int i = ; i <= n; ++i) {

            scanf("%d%d",&c[i],&d[i]);

            dinic.AddEdge(i+n,t,);

            for (int j = ; j <= n; ++j) {

                if (b[j] >= c[i] && a[j] > d[i]) {

                    dinic.AddEdge(j,i+n,);

                }

            }

        }

        int ans = dinic.maxflow(s,t);

        printf("%s\n",ans==n ? "Yes" : "No");

    }

    return ;

}