-
前言
写网络流，因为 rp 过低一直 TLE （悲）。
结果二分图过了。
顺手来一发二分图的题解。
-
题目大意
农夫约翰的 (N) 头牛各自居住在 (B) 个牛棚之一中。当然，这些牛棚容量有限制。一些牛喜欢它们目前居住的牛棚，另一些并不怎么喜欢。
约翰想重新安排这些牛，让它们尽可能同样高兴，甚至可以让它们全都讨厌指定的牛棚。
每头牛给约翰这些牛棚在它们心目中的位置(不会有两个牛棚在某头牛心目中处于同等位置)，一头牛的开心值为它所住牛棚在它心目中的位置。
你的任务就是牛(开心值最大值与最小值之差)的最小值。
-
分析
你的任务就是牛(开心值最大值与最小值之差)的最小值。
这句话很好想到二分。
所以我们可以二分差的最小值，再用 check 函数。
N头牛各自居住在B个牛棚之一中
一头牛对应一个牛棚，也就是二分图匹配。
所以，每次二分后，可以枚举每个区间，然后跑二分图匹配，判断匹配数是否为 (n) 。
这些牛棚容量有限制。
一个牛棚可以塞 (b_i) 只牛，换句话说，就是一个牛棚可以匹配 (b_i) 只牛。
所以在跑二分图匹配的时候，加一个 (cnt_i) 表示第 (i) 个牛棚已经匹配了 (cnt_i) 只牛。
然后就是二分图操作的时候还要枚举 (cnt_i) 只牛。
复杂度 (O(n^2m^2log_m)) 。
- 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int Maxn=1000+5;
int n,m,ans,mp[Maxn][25],b[Maxn];
int st,ed,cnt[Maxn],matched[25][Maxn];
bool vis[Maxn];
bool found(int x)
{
for(int i=st;i<=ed;i++)
{
int y=mp[x][i];
if(vis[y])continue;
vis[y]=1;
if(cnt[y]<b[y])
{
matched[y][++cnt[y]]=x;
return 1;
}
else{
for(int j=1;j<=cnt[y];j++)
if(found(matched[y][j]))
{
matched[y][j]=x;
return 1;
}
}
}
return 0;
}
int match()
{
int res=0;
memset(matched,0,sizeof(matched));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(found(i))res++;
}
return res;
}
bool check(int len)
{
for(st=1;st<=m;st++)
{ ed=st+len-1;
if(ed>m)break;
if(match()==n)return 1;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&mp[i][j]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
int l=0,r=m,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d
",ans);
return 0;
}
//沿着风的轨迹 乱舞蹁跹 困于死水之间
[ ext{by Rainy7}
]