题意:
给定若干个上限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;
}