SPOJ AMR12A The Black Riders --二分+二分图最大匹配

题意:有n个人,m个洞。每个洞能容纳一个人,每个人到每个洞需要花费一些时间。每个人到达一个洞后可以花C的时间来挖一个洞,并且最多挖一个洞,这样又能多容纳一人。求能使至少K个人进洞的最短时间。

解法:看到n个人和m个洞,并且人要进洞容易想到二分匹配,又是求极值的问题,应该是最大匹配。由于直接求极值不好求,可以将求极值问题转化为判定问题,即二分最短时间,然后判定能否达到。判定时,如果i到j的时间小于等于mid,就将i和j连一条边,如果T[i][j]+C <= mid 说明还来得及挖洞,将i和j+m连一条边,j+m为新挖的洞,每次判定要建一次图,然后求一个最大匹配,如果最大匹配数>=k,说明mid可行,继续往下二分。直到找到答案。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define N 107 vector<int> G[N];
int vis[*N],match[*N];
int mp[N][N];
int n,m,k,c; int Search_Path(int s)
{
for(int i=;i<G[s].size();i++)
{
int v = G[s][i];
if(!vis[v])
{
vis[v] = ;
if(match[v] == - || Search_Path(match[v]))
{
match[v] = s;
return ;
}
}
}
return ;
} int Max_match()
{
memset(match,-,sizeof(match));
int cnt = ;
for(int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
if(Search_Path(i))
cnt++;
}
return cnt;
} int check(int mid)
{
int i,j;
for(i=;i<=n;i++)
G[i].clear();
for(i=;i<=n;i++)
{
for(j=;j<=m;j++)
{
if(mp[i][j] <= mid)
G[i].push_back(j);
if(mp[i][j]+c <= mid)
G[i].push_back(j+m);
}
}
int cnt = Max_match();
if(cnt >= k)
return ;
return ;
} int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&m,&k,&c);
int maxi = -;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
{
scanf("%d",&mp[i][j]);
maxi = max(mp[i][j],maxi);
}
int low = ;
int high = maxi;
while(low<=high)
{
int mid = (low+high)/;
if(check(mid))
high = mid-;
else
low = mid+;
}
printf("%d\n",high+);
}
return ;
}
上一篇:asp.net中SQL语句太长,怎么换行写?


下一篇:关于SQLServer2008数据如何导入SQL2005的解决办法,高版本数据导入低版本中。