POJ 2289 :
| Description Jamie is a very popular girl and has quite a lot of friends, so she always keeps a very long contact list in her cell phone. The contact list has become so long that it often takes a long time for her to browse through the whole list to find a friend's number. As Jamie's best friend and a programming genius, you suggest that she group the contact list and minimize the size of the largest group, so that it will be easier for her to search for a friend's number among the groups. Jamie takes your advice and gives you her entire contact list containing her friends' names, the number of groups she wishes to have and what groups every friend could belong to. Your task is to write a program that takes the list and organizes it into groups such that each friend appears in only one of those groups and the size of the largest group is minimized. Input There will be at most 20 test cases. Ease case starts with a line containing two integers N and M. where N is the length of the contact list and M is the number of groups. N lines then follow. Each line contains a friend's name and the groups the friend could belong to. You can assume N is no more than 1000 and M is no more than 500. The names will contain alphabet letters only and will be no longer than 15 characters. No two friends have the same name. The group label is an integer between 0 and M - 1. After the last test case, there is a single line `0 0' that terminates the input. Output For each test case, output a line containing a single integer, the size of the largest contact group. Sample Input Source Shanghai 2004 |
二分多重匹配，最大值最小我们二分每组容量，然后判断。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int mod = 1000000007;
const int maxn=1100;
int mp[maxn][maxn];
int link[maxn][maxn],used[maxn];
int num[maxn];
int n,m;
bool dfs(int x)
{
REP(i,m)
{
if(mp[x][i]&&!used[i])
{
used[i]=1;
if(link[i][0]<num[i])
{
link[i][++link[i][0]]=x;
return true;
}
for(int j=1;j<=num[i];j++)
{
if(dfs(link[i][j]))
{
link[i][j]=x;
return true;
}
}
}
}
return false;
}
bool ok(int x)
{
int res=0;
for(int i=0;i<m;i++)
link[i][0]=0;
for(int i=0;i<m;i++)
num[i]=x;
for(int i=1;i<=n;i++)
{
CLEAR(used,0);
if(dfs(i)) res++;
}
return res==n;
}
int main()
{
char str[15],c;
int x;
while(~scanf("%d%d",&n,&m)&&(n+m))
{
CLEAR(mp,0);
CLEAR(num,0);
REPF(i,1,n)
{
scanf("%s",str);
while((c=getchar())!='\n')
{
scanf("%d",&x);
mp[i][x]=1;
}
}
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(ok(mid)) r=mid-1;
else l=mid+1;
}
printf("%d\n",l);
}
return 0;
}
POJ 3189 :
| Description Farmer John's N (1 <= N <= 1000) cows each reside in one of B (1 <= B <= 20) barns which, of course, have limited capacity. Some cows really like their current barn, and some are not so happy. FJ would like to rearrange the cows such that the cows are as equally happy as possible, even if that means all the cows hate their assigned barn. Each cow gives FJ the order in which she prefers the barns. A cow's happiness with a particular assignment is her ranking of her barn. 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. Input Line 1: Two space-separated integers, N and B Lines 2..N+1: Each line contains B space-separated integers which are exactly 1..B sorted into some order. The first integer on line i+1 is the number of the cow i's top-choice barn, the second integer on that line is the number of the i'th cow's second-choice barn, and so on. Line N+2: B space-separated integers, respectively the capacity of the first barn, then the capacity of the second, and so on. The sum of these numbers is guaranteed to be at least N. Output Line 1: One integer, the size of the minumum range of barn rankings the cows give their assigned barns, including the endpoints. Sample Input Hint Explanation of the sample: Each cow can be assigned to her first or second choice: barn 1 gets cows 1 and 5, barn 2 gets cow 2, barn 3 gets cow 4, and barn 4 gets cows 3 and 6. Source USACO 2006 February Gold |
求rank差值最小，我的枚举方法超时，看了网上的一种方法。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int mod = 1000000007;
const int maxn=1100;
int rank[maxn][maxn];
int link[maxn][maxn],used[maxn];
int num[maxn];
int n,b,low,high;
bool dfs(int x)
{
REPF(i,1,b)
{
if(!used[i]&&rank[x][i]>=low&&rank[x][i]<=high)
{
used[i]=1;
if(link[i][0]<num[i])
{
link[i][++link[i][0]]=x;
return true;
}
for(int j=1;j<=num[i];j++)
{
if(dfs(link[i][j]))
{
link[i][j]=x;
return true;
}
}
}
}
return false;
}
bool ok()
{
int res=0;
for(int i=1;i<=b;i++)
link[i][0]=0;
for(int i=1;i<=n;i++)
{
CLEAR(used,0);
if(dfs(i)) res++;
}
return res==n;
}
int main()
{
int x;
while(~scanf("%d%d",&n,&b))
{
REPF(i,1,n)
REPF(j,1,b)
{
scanf("%d",&x);
rank[i][x]=j;
}
REPF(i,1,b) scanf("%d",&num[i]);
// int flag=0,len;
// for(len=1;len<=b;len++)
// {
// for(int i=b;i-len+1>0;i--)
// {
// low=i-len+1;high=i;
// if(ok())
// {
// flag=1;
// break;
// }
// }
// if(flag) break;
// }
low=high=1;
int ans=0x3f3f3f3f;
while(low<=high&&high<=b)
{
if(ok())
{
ans=min(ans,high-low+1);
low++;
}
else high++;
}
printf("%d\n",ans);
}
return 0;
}
![[bzoj1433][ZJOI2009]假期的宿舍 二分图最大匹配[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)