Codeforces 628F Bear and Fair Set

题意:

给定若干个上限upto以及集合中在[1,upto]中的元素个数，问是否存在这样的集合使得集合中的元素除以5的余数的个数相等。

分析：

首先可以想到区间的数与其除以5的余数和区间编号分别一一对应，这样我们就可以在他们之间建立容量为1的边，而由于规定某个区间的元素个数，所以我们在源点和对应区间编号之间建立容量为元素个数的边，这样就满足题目中的限制条件。而要求余数个数相等，即均为n/5，在余数和汇点之间建立容量为n/5的边，直接用最大流求解即可~

代码：

#include<cstdio>

#include<iostream>

#include<queue>

#include<cmath>

#include<algorithm>

#include<vector>

#include<cstring>

using namespace std;

typedef pair<int, int>pii;

#define fi first

#define se second

struct edge{int to, cap, rev;};

const int maxn = 10005, maxm = 20100, INF = 0x3fffffff;

int d[maxm], iter[maxm];

int s, t;

int n, b, q;

vector<edge>G[maxm];

pii u[maxn];

void add_edge(int from, int to, int cap)

{

    G[from].push_back((edge){to, cap, G[to].size()});

    G[to].push_back((edge){from, 0, G[from].size()-1});

}

void bfs()

{

    memset(d, -1, sizeof(d));

    queue<int>q;

    d[s] = 0;

    q.push(s);

    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&&d[e.to]<0){

                d[e.to] = d[v] + 1;

                q.push(e.to);

            }

        }

    }

}

int dfs(int v, int f)

{

    if(v == t) return f;

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

        edge &e = G[v][i];

        if(e.cap > 0 && d[v] < d[e.to]){

            int tf = dfs(e.to, min(f, e.cap));

            if(tf > 0){

                e.cap -= tf;

                G[e.to][e.rev].cap +=tf;

                return tf;

            }

        }

    }

    return 0;

}

int max_flow()

{

    int flow = 0;

    for(;;){

        bfs();

        if(d[t]<0) return flow;

        memset(iter, 0, sizeof(iter));

        int f;

        while((f = dfs(s, INF))>0){

            flow += f;

        }

    }

}

int solve()

{

    for(int i = 0; i <= q; i++){

        int tmp = u[i].se - u[i - 1].se;

        if(tmp < 0) return 0;

        if(tmp > u[i].fi - u[i-1].fi) return 0;

        add_edge(s, i, tmp);

        for(int j = u[i - 1].fi + 1; j <= u[i].fi; j++){

            add_edge(i, q + j, 1);

            add_edge(q + j, j % 5 + b + q + 1, 1);

        }

    }

    for(int i = 0; i < 5; i++){

        add_edge(i + b + q + 1, t, n / 5);

    }

    return max_flow() == n;

}

int main (void)

{

    scanf("%d%d%d",&n, &b, &q);

    int upto, num;

    for (int i = 0; i < q; i++){

        scanf("%d%d", &upto, &num);

        u[i] = pii(upto,num);

    }

    sort(u, u + q);

    u[q] = pii(b, n);

    s = q + b + 6, t = s + 1;

    if(solve()) printf("fair\n");

    else printf("unfair\n");

    return 0;

}