CF628F Bear and Fair Set
eee_hoho
2021-03-20 09:37:01
感觉这题用不着高深的网络流建模技巧，直接二分图匹配不好吗。
考虑 $b$ 中每个数对每个余数匹配， $i\to i\%5$ ，流量为 $1$ 。
然后考虑对集合的限制，差分完之后可以得到每个区间恰好有几个数，设当前区间为 $[l,r]$ 建一个虚点 $x$ ， $S\to x$ ，流量为区间恰好的数的个数， $x\to i(l\le i\le r)$ ,流量为 $1$ 。
最后模数向 $T$ 连流量为 $\frac{n}{5}$ 的边。
我们还需要满足集合限制中的恰好，可以看作是一条边流量的上下界，直接跑有源有汇上下界可行流就行了。
跑的很快QAQ
**Code**
``` cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1e4;
const int inf = 1e9;
using namespace std;
struct qry
{
int u,t;
}a[N + 5];
int n,b,q,idc,id1[N + 5],S,T,id2[10],t[N + 5],fl[N * 10 + 5];
namespace F
{
const int N = 1e6;
const long long inf = 2e18;
struct edges
{
int to;
long long cost;
}edge[N * 2 + 5];
int nxt[N * 2 + 5],head[N + 5],edge_cnt = 1,dis[N + 5],q[N + 5],cur[N + 5],S,T;
void add_edge(int u,int v,long long w)
{
edge[++edge_cnt] = (edges){v,w};
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void add(int u,int v,long long w)
{
add_edge(u,v,w);
add_edge(v,u,0);
}
int bfs()
{
for (int i = 1;i <= idc;i++)
cur[i] = head[i],dis[i] = 0;
int l = 1,r = 0;
dis[S] = 1;
q[++r] = S;
while (l <= r)
{
int u = q[l++];
for (int i = head[u];i;i = nxt[i])
{
int v = edge[i].to,w = edge[i].cost;
if (w && !dis[v])
{
dis[v] = dis[u] + 1;
q[++r] = v;
}
}
}
return dis[T];
}
long long dfs(int u,long long flow)
{
if (u == T)
return flow;
long long sm = 0;
for (int &i = cur[u];i;i = nxt[i])
{
int v = edge[i].to;
long long w = edge[i].cost;
if (dis[v] == dis[u] + 1 && w)
{
long long res = dfs(v,min(w,flow));
edge[i].cost -= res;
edge[i ^ 1].cost += res;
sm += res;
flow -= res;
if (!flow)
break;
}
}
return sm;
}
long long dinic(int s,int t)
{
S = s;T = t;
long long ans = 0;
while (bfs())
ans += dfs(S,inf);
return ans;
}
void clear()
{
edge_cnt = 1;
for (int i = 1;i <= idc;i++)
head[i] = 0;
idc = 0;
}
bool check(int S,int T)
{
for (int i = head[S];i;i = nxt[i])
if (edge[i].cost)
return 0;
for (int i = head[T];i;i = nxt[i])
if (edge[i ^ 1].cost)
return 0;
return 1;
}
}
bool cmp(qry a,qry b)
{
return a.u < b.u;
}
int main()
{
scanf("%d%d%d",&n,&b,&q);
for (int i = 1;i <= q;i++)
scanf("%d%d",&a[i].u,&a[i].t);
S = ++idc;T = ++idc;
for (int i = 1;i <= b;i++)
id1[i] = ++idc;
for (int i = 0;i <= 4;i++)
id2[i] = ++idc;
for (int i = 1;i <= b;i++)
F::add(id1[i],id2[i % 5],1);
sort(a + 1,a + q + 1,cmp);
for (int i = 1;i <= q;i++)
{
if (!t[a[i].u])
t[a[i].u] = a[i].t;
else
{
if (t[a[i].u] != a[i].t)
{
cout<<"unfair"<<endl;
return 0;
}
}
if (a[i].u != a[i - 1].u)
{
int x = a[i].t - a[i - 1].t;
if (x < 0)
{
cout<<"unfair"<<endl;
return 0;
}
int nw = ++idc;
F::add(S,nw,0);
fl[S] -= x;
fl[nw] += x;
for (int j = a[i - 1].u + 1;j <= a[i].u;j++)
F::add(nw,id1[j],1);
}
}
for (int i = a[q].u + 1;i <= b;i++)
F::add(S,id1[i],1);
for (int i = 0;i <= 4;i++)
{
F::add(id2[i],T,0);
fl[id2[i]] -= n / 5;
}
F::add(T,S,inf);
fl[T] = n;
int ss = ++idc,tt = ++idc;
for (int i = 1;i <= idc;i++)
if (fl[i] < 0)
F::add(i,tt,-fl[i]);
else
if (fl[i] > 0)
F::add(ss,i,fl[i]);
int x = F::dinic(ss,tt);
if (F::check(ss,tt))
cout<<"fair"<<endl;
else
cout<<"unfair"<<endl;
return 0;
}
```