A Plug for UNIX

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

const int N = 510, M = 20010, INF = 0x3f3f3f3f;

int n, m, k, S, T;
char str[30], str2[30];
int h[N], e[M], ne[M], f[M], idx;
int q[N], d[N], pre[N];
bool st[N];
map<string, int> mp;

void add(int a, int b, int c) {
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs() {
    int hh = 0, tt = 0;
    memset(st, false, sizeof st);
    q[0] = S, st[S] = true, d[S] = INF;

    while (hh <= tt) {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i]) {

            int ver = e[i];

            if (!st[ver] && f[i]) {
                st[ver] = true;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;

                if (ver == T)
                    return true;
                q[ ++ tt] = ver;
            }
        }
    }

    return false;
}

int EK() {
    int r = 0;

    while (bfs()) {
        r += d[T];

        for (int i = T; i != S; i = e[pre[i] ^ 1])

            f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
    }

    return r;
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);

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

        scanf("%s", str);
        mp[str] = i;
    }

    int id = n;
    scanf("%d", &m);

    for (int i = 1; i <= m; i ++ ) {

        scanf("%s %s", str, str2);

        if (!mp.count(str2))
            mp[str2] = ++ id;
        add(i, m + mp[str2], 1);
    }

    scanf("%d", &k);

    for (int i = 1; i <= k; i ++ ) {

        scanf("%s %s", str, str2);

        if (!mp.count(str))
            mp[str] = ++ id;

        if (!mp.count(str2))
            mp[str2] = ++ id;
        add(m + mp[str], m + mp[str2], INF);
    }

    for (int i = 1; i <= m; i ++ )

        add(0, i, 1);

    for (int i = m + 1; i <= m + n; i ++ )

        add(i, m + id + 1, 1);
    S = 0, T = m + id + 1;
    printf("%d\n", m - EK());
    return 0;
}

COURSES

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310, M = 30010;

int n, p;
int st[N];
int match[N];
bool g[N][N];

int find (int x) {
    for (int i = 1; i <= n; i ++ )

        if (g[x][i])
            if (!st[i]) {
                st[i] = true;

                if (match[i] == 0 || find(match[i])) {
                    match[i] = x;
                    return true;
                }
            }

    return false;
}

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

    while (T -- ) {
        memset(match, 0, sizeof match);
        memset(g, false, sizeof g);
        scanf("%d%d", &p, &n);

        for (int i = 1; i <= p; i ++ ) {

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

            while (k -- ) {
                int b;
                scanf("%d", &b);
                g[i][b] = true;
            }
        }

        if (n < p) {
            puts("NO");
            continue;
        }

        int res = 0;

        for (int i = 1; i <= p; i ++ ) {

            memset(st, false, sizeof st);

            if (find(i))
                res ++ ;
        }

        if (res == p)
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

Sorting Slides

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3 + 10;

struct node {
    int x1, x2, y1, y2;
} a[N];

int n;
int st[N];
int match[N];
bool g[N][N];
int casei;

int find (int x) {
    for (int i = 1; i <= n; i ++ )

        if (g[x][i])
            if (!st[i]) {
                st[i] = true;

                if (match[i] == 0 || find(match[i])) {
                    match[i] = x;
                    return true;
                }
            }

    return false;
}

int sum() {
    int res = 0;
    memset(match, 0, sizeof match);

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

        memset(st, false, sizeof st);

        if (find(i))
            res ++ ;
    }

    return res;
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;
        memset(g, false, sizeof g);

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

            scanf("%d%d%d%d", &a[i].x1, &a[i].x2, &a[i].y1, &a[i].y2);

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

            int x, y;
            scanf("%d%d", &x, &y);

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

                if (x >= a[j].x1 && x <= a[j].x2 && y >= a[j].y1 && y <= a[j].y2)
                    g[j][i] = true;
        }

        printf("Heap %d\n", ++ casei);
        int ans = sum();
        bool flag = false;

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

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

                if (g[i][j]) {
                    g[i][j] = false;
                    int temp = sum();

                    if (temp != ans) {
                        if (!flag)
                            flag = true;
                        else
                            printf(" ");
                        printf("(%c,%d)", 'A' + i - 1, j);
                    }

                    g[i][j] = true;
                }

        if (!flag)
            printf("none");
        printf("\n\n");
    }

    return 0;
}