「Poj3189」Steady Cow Assignment

来源和评测点

USACO 2006 February Gold
Poj3189
Caioj1120

题目

「题目大意」
有N(1<=N<=1000)头牛,B(1<=B<=20)个牛圈
每头牛对于牛圈都有不同的喜好程度排名,牛圈有一定的容量

对于某种分配方案,假如牛1去了牛圈3,是它的第五志愿,记满意程度=5
输出(所有牛的满意程度 最大值到最小值的区间)的最小值

相当于 (MAX牛的满意程度)-(MIN牛的满意程度)+1

重点句:
Your job is to find an assignment of cows to barns such that no barn’s capacity is exceeded and the size of the range (i.e., one more than the positive difference between the the highest-ranked barn chosen and that lowest-ranked barn chosen) of barn rankings the cows give their assigned barns is as small as possible.
「输入格式」
第一行N和B
接下来N行,每行B个数,表示喜欢的牛圈的序号,按喜欢的程度(递减)给出,
(比如第一个给出的牛圈的就是最喜欢,最后一个就是最不喜欢的)
接下来B个数,每个数表示牛圈最多容纳的牛的数目
「输出格式」
最小的“满意程度区间”
「输入样例」
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:牛1 牛5
牛圈2:牛2
牛圈3:牛4
牛圈4:牛3 牛6
满意程度 1 1 1 1 1 2
答案就是 2

分析

网络流教程和题目分类参见:
「OI之路」03图论算法-4网络流
其他网络流题目参见:Tag-网络流

其实可以尝试着看看英文题
题意我翻译好了,caioj不完整也不好理解,POJ全英文

对于区间,枚举下界,在此基础上二分答案
O( B*logB*(n^3) )
这做法真的狗血,好久没用过枚举了

构图:
源点到牛连权值为1的边
牛到牛圈连权值为1的边
牛圈到汇点连权值为 该牛圈容量 的边

代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=1100,MAXM=61000;
int mymin(int x,int y) {return x<y?x:y;}

struct pt
{
int h;
int hou;
}p[MAXN];
struct rod
{
int y,c,g;
int oth;
}e[MAXM];
int ln;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;

ln++;
e[ln].y=x;e[ln].c=0;
e[ln].g=p[y].hou;p[y].hou=ln;

e[ln].oth=ln-1;e[ln-1].oth=ln;
}
int st,ed;
int lst[MAXN];
bool bfs()
{
for(int i=1;i<=ed;i++) p[i].h=0;

int tou=1,wei=1;
lst[1]=st;p[st].h=1;
while(tou<=wei)
{
int x=lst[tou];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].h==0 and e[k].c>0)
{
p[y].h=p[x].h+1;
lst[++wei]=y;
}
}
tou++;
}
return p[ed].h>0;
}
int dfs(int x,int f)
{
if(x==ed) return f;
int t=0;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].h==p[x].h+1 and e[k].c>0 and t<f)
{
int tt=dfs(y,mymin(f-t,e[k].c));
t+=tt;e[k].c-=tt;e[e[k].oth].c+=tt;
}
}
if(t==0) p[x].h=0;
return t;
}

int n,b;
int lv[MAXN][30];
int ct[30];
bool check(int ll,int rr)
{
ln=0;for(int i=1;i<=ed;i++) p[i].hou=0;
for(int i=1;i<=n;i++)
{
ins(st,i,1);
for(int j=ll;j<=rr;j++) ins(i, n+lv[i][j] ,1);
}
for(int i=1;i<=b;i++) ins(n+i,ed,ct[i]);

int ans=0;
while( bfs() ) ans+=dfs(st,INF);
//printf("-----ll=%d rr=%d ans=%d n=%d\n",ll,rr,ans,n);
return ans==n;
}
int getans(int low)
{
int l=1,r=b-low+1,ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(low,low+mid-1)) ans=mid,r=mid-1;
else l=mid+1;
}
//printf("low=%d ans=%d\n",low,ans);
return ans<0?INF:ans;
}
int main()
{
scanf("%d%d",&n,&b);
for(int i=1;i<=n;i++)
for(int j=1;j<=b;j++)
scanf("%d",&lv[i][j]);
for(int i=1;i<=b;i++) scanf("%d",&ct[i]);

st=n+b+1,ed=n+b+2;

int mi=INF;
for(int i=1;i<=b;i++) mi=mymin(mi, getans(i) );

printf("%d",mi);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b6a3.html
转载请注明出处,谢谢!