Luogu SP839 OPTM - Optimal Marks(按位最小割)

这道题和 BZOJ 2400 是一道题,不多讲了

CODE

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

typedef long long LL;

template<typename T>inline void read(T &num) {

    char ch; int flg=1;

    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;

    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());

    num*=flg;

}

const int inf = 1e9;

const int MAXN = 505;

const int MAXM = 30005;

int n, m, fir[MAXN], S, T, cnt;

struct edge { int to, nxt; int c; }e[MAXM];

inline void add(int u, int v, int cc, int rc=0) {

    e[cnt] = (edge){ v, fir[u], cc }; fir[u] = cnt++;

    e[cnt] = (edge){ u, fir[v], rc }; fir[v] = cnt++;

}

int dis[MAXN], vis[MAXN], info[MAXN], cur, q[MAXN];

inline bool bfs() {

    int head = 0, tail = 0;

    vis[S] = ++cur; q[tail++] = S;

    while(head < tail) {

        int u = q[head++];

        for(int i = fir[u]; ~i; i = e[i].nxt)

            if(e[i].c && vis[e[i].to] != cur)

                vis[e[i].to] = cur, dis[e[i].to] = dis[u] + 1, q[tail++] = e[i].to;

    }

    if(vis[T] == cur) memcpy(info, fir, (T+1)<<2);

    return vis[T] == cur;

}

int dfs(int u, int Max) {

    if(u == T || !Max) return Max;

    int flow=0, delta;

    for(int &i = info[u]; ~i; i = e[i].nxt)

        if(e[i].c && dis[e[i].to] == dis[u] + 1 && (delta=dfs(e[i].to, min(e[i].c, Max-flow)))) {

            e[i].c -= delta, e[i^1].c += delta, flow += delta;

            if(flow == Max) return flow;

        }

    return flow;

}

inline int dinic() {

    memset(vis, 0, sizeof vis);

    int flow=0, x;

    while(bfs()) {

        while((x=dfs(S, inf))) flow+=x;

    }

    return flow;

}

int A[MAXN], X[3005], Y[3005], ans[MAXN];

bool flg[MAXN];

void Getans(int u, int val) {

    ans[u] += val; flg[u] = 1;

    for(int i = fir[u]; ~i; i = e[i].nxt)

        if(e[i].c && !flg[e[i].to])

            Getans(e[i].to, val);

}

int main () {

    int kase;

    read(kase);

    while(kase--) {

        read(n); read(m); S = 0, T = n+1;

        memset(A, -1, sizeof A);

        for(int i = 1; i <= m; ++i) read(X[i]), read(Y[i]);

        int tot, x, y;

        read(tot); while(tot--) read(x), read(y), A[x] = y;

        for(int bit = 0; bit < 31; ++bit) {

            memset(fir, -1, sizeof fir); cnt = 0;

            for(int i = 1; i <= m; ++i) add(X[i], Y[i], 1, 1);

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

                if(A[i] < 0) continue;

                if(A[i]&(1<<bit)) add(S, i, inf);

                else add(i, T, inf);

            }

            memset(flg, 0, sizeof flg);

            dinic(); Getans(S, 1<<bit);

        }

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

            printf("%d\n", ans[i]), ans[i] = 0;

    }

}