牛棚安排

jzoj 1259

題目大意：

有$n$頭牛和$m$個牛棚，每頭牛有自己第1喜歡，第2喜歡……第$m$喜歡的牛棚（開心度分別為$m,m?1,m?2\dots \dots 1$），然后讀入$m$個數表示第$i$個牛棚最多可以進多少頭牛，現在讓所有牛都進入到牛棚內，問最開心的牛和最傷心的牛開心度之差最小是多少

輸入樣例

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

輸出樣例

2

樣例解釋

每頭奶牛都能被安排進她的第一或第二喜歡的牛棚。下面給出一種合理的分配方案：奶牛1和奶牛5住入牛棚1，牛棚2由奶牛2獨占，奶牛4住進牛棚3，剩下的奶牛3和奶牛6安排到牛棚4。

解題思路

先二分枚舉答案，然后枚舉每一個區間，接下來用最大流求二分圖的匹配即可

代碼

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int n, m, l, r, mid, sum, s, t, tot, b[50], head[2000], dep[2000], v[2100][50];const int inf = 1 << 29;struct rec {int to, next, edge; }a[40500];queue<int> d;void add(int x, int y, int z) {a[++tot].to = y;a[tot].edge = z;a[tot].next = head[x];head[x] = tot;a[++tot].to = x;a[tot].edge = 0;a[tot].next = head[y];head[y] = tot; }bool bfs() {memset(dep, 0, sizeof(dep));while(!d.empty()) d.pop();d.push(s);dep[s] = 1;while (!d.empty()){int h = d.front();d.pop();for (int i = head[h]; i; i = a[i].next)if (!dep[a[i].to] && a[i].edge){dep[a[i].to] = dep[h] + 1;if (a[i].to == t) return true;d.push(a[i].to);}}return false; }int dinic(int x, int flow) {if (x == t) return flow;int rest = 0, k;for (int i = head[x]; i; i = a[i].next)if (dep[x] + 1 == dep[a[i].to] && a[i].edge){k = dinic(a[i].to, min(a[i].edge, flow - rest));if (!k) dep[a[i].to] = 0;rest += k;a[i].edge -= k;a[i^1].edge += k;if (rest == flow) return rest;}return rest; }bool js(int x) {s = 0;t = n + m + 1;for (int i = 1; i <= m - x + 1; ++i)//開頭位置{memset(head, 0, sizeof(head));tot = 0;for (int j = 1; j <= m; ++j)add(n + j, t, b[j]);//連到Tfor (int j = 1; j <= n; ++j){add(s, j, 1);//連到Sfor (int k = i; k - i + 1 <= x; ++k)add(j, n + v[j][k], 1);//連邊}sum = 0;while(bfs())//找增廣路sum += dinic(s, inf);//流if (sum == n) return true;//可以滿足}return false; } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)scanf("%d", &v[i][j]);//先存下來，到時再連邊for (int i = 1; i <= m; ++i)scanf("%d", &b[i]);l = 1;r = m;while(l < r)//二分枚舉{mid = (l + r) >> 1;if (js(mid)) r = mid;else l = mid + 1;}printf("%d", l);return 0; }

總結

以上是生活随笔為你收集整理的【最大流】牛棚安排（jzoj 1259）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。