首页 > 代码库 > SPOJ AMR12A The Black Riders --二分+二分图最大匹配
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 107vector<int> G[N];int vis[2*N],match[2*N];int mp[N][N];int n,m,k,c;int Search_Path(int s){ for(int i=0;i<G[s].size();i++) { int v = G[s][i]; if(!vis[v]) { vis[v] = 1; if(match[v] == -1 || Search_Path(match[v])) { match[v] = s; return 1; } } } return 0;}int Max_match(){ memset(match,-1,sizeof(match)); int cnt = 0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(Search_Path(i)) cnt++; } return cnt;}int check(int mid){ int i,j; for(i=0;i<=n;i++) G[i].clear(); for(i=1;i<=n;i++) { for(j=1;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 1; return 0;}int main(){ int t,i,j; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&n,&m,&k,&c); int maxi = -1; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&mp[i][j]); maxi = max(mp[i][j],maxi); } int low = 0; int high = maxi; while(low<=high) { int mid = (low+high)/2; if(check(mid)) high = mid-1; else low = mid+1; } printf("%d\n",high+1); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。