POJ 3189. Steady Cow Assignment

发表于 更新于 分类于

链接

http://poj.org/problem?id=3189

题意

将 $n$ 头牛分配给 $m$ 个谷仓，每个谷仓容量不同，给出每头牛对于 $m$ 个谷仓喜欢程度的排名。

求最小区间（选择的最大喜欢程度的排名 - 最小喜欢程度的排名）。

思路

二分图多重匹配，双指针。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <climits>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <bitset>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=1005;
const int M=25;
int n,m,f[N][M],cap[M],cnt[M],match[M][N];
bool st[M];
bool dfs(int u,int l,int r) {
    for(int i=l;i<=r;i++) {
        int v=f[u][i];
        if(st[v]) continue;
        st[v]=true;
        if(cnt[v]<cap[v]) {
            match[v][++cnt[v]]=u;
            return true;
        }
        for(int i=1;i<=cnt[v];i++)
            if(dfs(match[v][i],l,r)) {
                match[v][i]=u;
                return true;
            }
    }
    return false;
}
bool check(int l,int r) {
    for(int i=1;i<=m;i++) cnt[i]=0;
    int res=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) st[j]=false;
        if(dfs(i,l,r)) res++;
    }
    if(res==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",&f[i][j]);
    for(int i=1;i<=m;i++) scanf("%d",&cap[i]);
    int l=1,r=1,res=0x3f3f3f3f;
    while(l<=r&&r<=m) {
        if(check(l,r)) res=min(res,r-l+1),l++;
        else r++;
    }
    printf("%d\n",res);
    return 0;
}