MENU

没有上司的舞会

20181103A task.pdf

将每个人拆为作为下属和作为上司两个点,下属向所有上司连边,跑二分图最大独立集。

#include<cstdio>
#include<queue>
#include<cstring>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#define inline __attribute__((always_inline))
#endif
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) { *oS++ = x; }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48; c = gc());
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { *oS++ = '0'; return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {
#ifndef ONLINE_JUDGE
        freopen("dance.in", "r", stdin), freopen("dance.out", "w", stdout);
#endif
    }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int N = ip.rd<int>(), M = ip.rd<int>(), cnt = 1, vis[201][201], x, y, s = 0, t = 2 * N + 1, head[402], dep[402], q[402], he, ta, cur[402], sz = 4 * (t - s + 1), ans;
struct edge {
    int v, w, next;
    edge(int v = 0, int w = 0, int next = 0) :v(v), w(w), next(next) {}
}e[80400];
inline void addedge(int u, int v, int w) { e[++cnt] = edge(v, w, head[u]), head[u] = cnt, e[++cnt] = edge(u, 0, head[v]), head[v] = cnt; }
inline int bfs() {
    memset(dep, 0, sizeof dep), dep[s] = 1, q[he = ta = 0] = s;
    while (he <= ta) {
        x = q[he++];
        for (int i = head[x]; i; i = e[i].next) {
            y = e[i].v;
            if (e[i].w > 0 && !dep[y]) {
                dep[y] = dep[x] + 1;
                if (y == t)return 1;
                q[++ta] = y;
            }
        }
    }
    return 0;
}
template<class T>inline T min(T a, T b) { return a < b ? a : b; }
int dfs(int x, int flow) {
    if (!flow || x == t)return flow;
    int ret = 0, f;
    for (int &i = cur[x]; i; i = e[i].next) {
        y = e[i].v;
        if (e[i].w && dep[y] == dep[x] + 1) {
            f = dfs(y, min(e[i].w, flow - ret)), e[i].w -= f, e[i ^ 1].w += f, ret += f;
            if (ret == flow)break;
        }
    }
    return ret;
}
int main() {
    while (M--)x = ip.rd<int>(), y = ip.rd<int>(), vis[x][y] = 1;
    for (int k = 1; k <= N; ++k)for (int i = 1; i <= N; ++i)for (int j = 1; j <= N; ++j)if (!vis[i][j] && i != j && i != k && j != k)vis[i][j] = vis[i][k] & vis[k][j];
    for (int i = 1; i <= N; ++i)for (int j = 1; j <= N; ++j)if (vis[i][j])addedge(i, j + N, 1);
    for (int i = 1; i <= N; ++i)addedge(s, i, 1), addedge(i + N, t, 1);
    while (bfs())memcpy(cur, head, sz), ans += dfs(s, 0x7fffffff);
    ip.print(N - ans);
}
Leave a Comment

captcha
请输入验证码