首页 > 代码库 > hdu2236 无题II 最大匹配 + 二分搜索
hdu2236 无题II 最大匹配 + 二分搜索
中文题目，题意大家都明白。
看到“不同的行和列”就觉得要用二分匹配来做。要求最大值与最小值的差值最小，是通过枚举边的下限和上限来完成。
枚举过程是这样的，在输入的过程可以记录下边权的最大值MAX和最小值MIN。那么他们的边权的差值的最大值为right = MAX -MIN ,最小值left =0。然后不断地增加边的下限，查找边权的差值，如果能得到完美匹配（匹配数等于n）,那么就记录下这个差值。最后输出。这个搜索过程类似于最大流+二分搜索。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int N=105,INF=0x3f3f3f3f; 8 int Map[N][N],cx[N],cy[N],dx[N],dy[N]; 9 bool bmask[N],bmap[N][N]; 10 int nx,ny,dis,ans; 11 bool searchpath() 12 { 13 queue<int> q; 14 dis=INF; 15 memset(dx,-1,sizeof(dx)); 16 memset(dy,-1,sizeof(dy)); 17 for(int i=1;i<=nx;i++) 18 { 19 if(cx[i]==-1){ q.push(i); dx[i]=0; } 20 while(!q.empty()) 21 { 22 int u=q.front(); q.pop(); 23 if(dx[u]>dis) break; 24 for(int v=1;v<=ny;v++) 25 { 26 if(bmap[u][v]&&dy[v]==-1) 27 { 28 dy[v]= dx[u] + 1; 29 if(cy[v]==-1) dis=dy[v]; 30 else 31 { 32 dx[cy[v]]= dy[v]+1; 33 q.push(cy[v]); 34 } 35 } 36 } 37 } 38 } 39 return dis!=INF; 40 } 41 int findpath(int u) 42 { 43 for(int v=1;v<=ny;v++) 44 { 45 if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1) 46 { 47 bmask[v]=1; 48 if(cy[v]!=-1&&dy[v]==dis) continue; 49 if(cy[v]==-1||findpath(cy[v])) 50 { 51 cy[v]=u; cx[u]=v; 52 return 1; 53 } 54 } 55 } 56 return 0; 57 } 58 void maxmatch() 59 { 60 ans=0; 61 memset(cx,-1,sizeof(cx)); 62 memset(cy,-1,sizeof(cy)); 63 while(searchpath()) 64 { 65 memset(bmask,0,sizeof(bmask)); 66 for(int i=1;i<=nx;i++) 67 if(cx[i]==-1) ans+=findpath(i); 68 } 69 } 70 void init() 71 { 72 memset(bmap,0,sizeof(bmap)); 73 } 74 75 int main() 76 { 77 //freopen("test.txt","r",stdin); 78 int i,j,k,n,cas,a,b; 79 scanf("%d",&cas); 80 while(cas--) 81 { 82 scanf("%d",&n); 83 a=100,b=0; 84 for(i=1;i<=n;i++) 85 for(j=1;j<=n;j++){ 86 scanf("%d",&Map[i][j]); 87 a=min(a,Map[i][j]); 88 b=max(b,Map[i][j]); 89 } 90 nx=ny=n; 91 int L=0,R=b-a,mid,flag,res; 92 while(L<=R) 93 { 94 mid=(L+R)/2; 95 flag=0; 96 for(k=a;k<=b;k++) 97 { 98 for(i=1;i<=n;i++) 99 for(j=1;j<=n;j++)100 if(Map[i][j]>=k&&Map[i][j]<=k+mid) bmap[i][j]=1;101 else bmap[i][j]=0;102 maxmatch();103 if(ans==n) {flag=1;break;}104 }105 if(flag) {res=mid;R=mid-1;}106 else L=mid+1;107 }108 printf("%d\n",res);109 }110 return 0;111 }
hdu2236 无题II 最大匹配 + 二分搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。