首页 > 代码库 > hdu 无题II(二分差值+最大匹配)
hdu 无题II(二分差值+最大匹配)
http://acm.hdu.edu.cn/showproblem.php?pid=2236
找n个数使得这n个数都在不同的行和列里显然是二分图模型。难点在于求最大值与最小值差值最小。这里二分差值(看的题解),进行试探是否可以匹配成功。
#include <stdio.h> #include <algorithm> #include <set> #include <map> #include <vector> #include <math.h> #include <string.h> #include <queue> #define LL long long #define _LL __int64 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1000000007; const int maxn = 110; int n; int G[maxn][maxn]; int Max,Min; int cur,mid; int match[10010],chk[10010]; int dfs(int p) { for(int i = 1; i <= n; i++) { if(!chk[i] && G[p][i] >= cur && G[p][i] <= cur+mid) { chk[i] = 1; if(match[i] == -1 || dfs(match[i])) { match[i] = p; return 1; } } } return 0; } int OK(int cur) { memset(match,-1,sizeof(match)); for(int i = 1; i <= n; i++) { memset(chk,0,sizeof(chk)); if(!dfs(i)) return 0; } return 1; } int main() { int test; scanf("%d",&test); while(test--) { scanf("%d",&n); Max = -1; Min = 110; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d",&G[i][j]); if(G[i][j] > Max) Max = G[i][j]; if(G[i][j] < Min) Min = G[i][j]; } } int l,r; l = 0; r = Max - Min; int res; while(l <= r) { mid = (l+r) >> 1; int flag = 0; for(cur = Min; cur + mid <= Max; cur++) //枚举最小值,检查当前差值是否可以匹配成功 { if( OK(cur) ) { flag = 1; break; } } if(flag) //匹配成功,更新r { res = mid; r = mid-1; } else l = mid+1;//匹配不成功,更新l } printf("%d\n",res); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。