[洛谷 P2857][caioj 1120] 牛选牛圈

[洛谷 P2857][caioj 1120] 牛选牛圈

【问题描述】

有N(1 <= N <= 1000) 头牛，B (1 <= B <= 20)个牛圈。
每头牛对于牛圈都有不同的喜好值(最喜欢为1，最不喜欢为B）。牛圈有一定的容量。
现在分配每头牛到牛圈去，要求所有牛的最大喜好值与最低喜好值的差值最小。输出最小的“喜好值差”。

【输入格式】
第一行N和B
下来N行，每行B个数。表示喜欢的牛圈的序号，按喜欢的程度（递减）给出，比如第一个给出的牛圈的就是最喜欢，最后一个就是最不喜欢的。
下来B个数，每个数表示牛圈最多容纳的牛的数目。

【输出格式】
输出最小的“喜好值差”。
Sample Input
6 4
1 2 3 4
2 3 1 4
4 2 3 1
3 1 2 4
1 3 4 2
1 4 2 3
2 1 3 2
Sample Output
2

分析

二分喜好差并枚举范围，然后用最大流判断可行

代码

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>#define IL inline
#define INF 0x7f7f7f7f
#define open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define close fclose(stdin); fclose(stdout);using namespace std;inline int read()
{char c=getchar();int sum=0,k=1;for(;'0'>c || c>'9';c=getchar())if(c=='-') k=-1;for(;'0'<=c && c<='9';c=getchar()) sum=sum*10+c-'0';return sum*k;
}int n, m, S, T;
int fond[1005][25];
int num[1005];struct Edge
{int to, nxt;int cap, flow;IL Edge(int v = 0, int nxt_ = 0, int c = 0, int f = 0){to = v; nxt = nxt_; cap = c; flow = f;}
}edge[42100];
int last[2100];
int cnt;
IL void add(int u, int v, int c)
{edge[cnt] = Edge(v, last[u], c, 0); last[u] = cnt++;edge[cnt] = Edge(u, last[v], 0, 0); last[v] = cnt++;
}int dep[2100];
int cur[2100];IL int min_(int x, int y) { return x < y ? x : y; }IL bool Bfs()
{queue<int>Q;memset(dep, 0, sizeof(dep));dep[S] = 1;Q.push(S);for(int t = 1, u; t;){u = Q.front(); Q.pop(); --t;for(int i = last[u]; i != -1; i = edge[i].nxt)if(!dep[edge[i].to] && edge[i].cap > edge[i].flow){dep[edge[i].to] = dep[u] + 1;Q.push(edge[i].to); ++t;}}return dep[T];
}IL int Dfs(int u, int a)
{if(u == T || !a) return a;int flow = 0, f;for(int &i = cur[u]; i != -1; i = edge[i].nxt)if(dep[edge[i].to] == dep[u] + 1 && (f = Dfs(edge[i].to, min_(a, edge[i].cap - edge[i].flow))) > 0){edge[i].flow += f;edge[i ^ 1].flow -= f;flow += f;if(!(a -= f)) break;}return flow;
}IL int maxflow()
{int flow = 0;for(; Bfs();){for(int i = S; i <= T; ++i) cur[i] = last[i];flow += Dfs(S, INF);}return flow;
}IL bool check(int mid)
{for(int l = 1, r; l + mid -1 <= m; ++l){r = l + mid - 1;memset(last, -1, sizeof(last)); cnt = 0;for(int i = 1; i <= m; ++i) add(i + n, T, num[i]);for(int i = 1; i <= n; ++i){add(S, i, 1);for(int j = l; j <= r; ++j)add(i, n + fond[i][j], 1);}if(maxflow() == n) return 1;}return 0;
}int main()
{open("1120");n = read(); m = read();S = 0; T = n + m + 1;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)fond[i][j] = read();for(int i = 1; i <= m; ++i) num[i] = read();int ans = -1;for(int l = 1, r = m, mid; l <= r;){mid = (l + r) >> 1;if(check(mid)){ans = mid;r = mid -1;}elsel = mid + 1;}printf("%dn", ans);close;return 0;
}