luoguP2857 Steady Cow Assignment G
题目描述:
有 \(N\) 头牛, \(B\) 个牛棚。告诉你每头牛心里牛棚的座次,即哪个牛棚他最喜欢,哪个第二喜欢, 哪个第三喜欢,等等。但牛棚容量一定,所以每头牛分配到的牛棚在该牛心中的座次有高有低。现在求一种最公平的方法分配牛到牛棚,使所有牛中,所居牛棚的座次最高与最低的跨度最小。
其中 \(1\le N \le 1000 , 1\le B \le 20\)。
解法:
直接求好像是不大好做,所以我们考虑二分答案,二分这个最小的跨度是多少。如果当前跨度不行,就更改左端点,否则就更改右端点。
关于判断当前这个跨度是否可行的时候,我们要枚举到这个跨度所有可能出现的情况。比如当前枚举到的跨度是 \(d\),那么我们要枚举 \(1\sim d,2\sim d+1,3\sim d+2,\cdots,B-d+1\sim B\) 这所有的情况,然后把所有的牛的喜欢度在当前这个情况的区间的连边。
然后如何判断当前这种连边情况是否合法呢,我们考虑使用网络流。
把源点连向牛,容量是一,因为一条边只会连一头牛。
把牛棚连向汇点,容量是牛棚的容量。
牛与牛棚的连边任意(只要不为零即可)。
如果说当前这种情况的最大流等于 \(N\),那么说明所有连向牛的边都能连向汇点,意味着这种情况是可以的,所以这个跨度就是可以的,之后继续二分就可以了。
注意事项:
每次跑完最大流的时候记得清空当前连的边。
记得二分跨度的时候从零开始(虽然好像洛谷的数据从一开始也能过)。
Code:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std ;
int n , m , a[1005][25] , b[25] , dis[1025] ;
struct Edge
{
int nxt , to , len ;
} edge[400005] ;
int cnt = 1 , head[1025] ;
void insert ( int u , int v , int w )
{
edge [ ++ cnt ] .nxt = head [ u ] ;
edge [ cnt ] .to = v ;
edge [ cnt ] .len = w ;
head [ u ] = cnt ;
}
queue < int > q ;
bool bfs ( )
{
memset ( dis , 0 , sizeof ( dis ) ) ;
dis [ 0 ] = 1 ;
q .push ( 0 ) ;
while ( ! q .empty ( ) )
{
int x = q .front ( ) ; q .pop ( ) ;
for ( int i = head [ x ] ; i ; i = edge [ i ] .nxt )
{
int y = edge [ i ] .to ;
if ( ! edge [ i ] .len || dis [ y ] )
continue ;
dis [ y ] = dis [ x ] + 1 ;
q .push ( y ) ;
}
}
return dis [ n + m + 1 ] ;
}
int dfs ( int x , int now )
{
if ( x == n + m + 1 )
return now ;
int res = now ;
for ( int i = head [ x ] ; i && res ; i = edge [ i ] .nxt )
{
int y = edge [ i ] .to ;
if ( ! edge [ i ] .len || dis [ y ] != dis [ x ] + 1 )
continue ;
int w = dfs ( y , min ( res , edge [ i ] .len ) ) ;
if ( ! w ) dis [ y ] = 0 ;
edge [ i ] .len -= w ;
edge [ i ^ 1 ] .len += w ;
res -= w ;
}
return now - res ;
}
int main ( )
{
cin >> n >> m ;
for ( int i = 1 ; i <= n ; ++ i )
for ( int j = 1 ; j <= m ; ++ j )
{
cin >> a [ i ] [ j ] ;
a [ i ] [ j ] += n ;
}
for ( int i = 1 ; i <= m ; ++ i )
cin >> b [ i ] ;
int l = 0 , r = m , mid ;
while ( l < r )
{
mid = ( l + r ) >> 1 ;
for ( int i = 0 ; i <= m - mid ; ++ i )
{
memset ( head , 0 , sizeof ( head ) ) ;
cnt = 1 ;
for ( int u = 1 ; u <= n ; ++ u )
for ( int j = 1 ; j <= mid ; ++ j )
insert ( u , a [ u ] [ i + j ] , 1000 ) , insert ( a [ u ] [ i + j ] , u , 0 ) ;
for ( int u = 1 ; u <= n ; ++ u )
insert ( 0 , u , 1 ) , insert ( u , 0 , 0 ) ;
for ( int u = n + 1 ; u <= n + m ; ++ u )
insert ( u , n + m + 1 , b [ u - n ] ) , insert ( n + m + 1 , u , 0 ) ;
int tmp = 0 , ans = 0 ;
while ( bfs ( ) )
ans += dfs ( 0 , 2000 ) ;
if ( ans == n )
{
r = mid ;
break ;
}
}
if ( r != mid )
l = mid + 1 ;
}
cout << r << '\n' ;
return 0 ;
}