题目描述

小凸和小方是好朋友，小方给了小凸一个 $n$ × $m$ $(n\le m)$ 的矩阵 $A$ ，并且要求小凸从矩阵中选出 $n$ 个数，其中任意两个数都不能在同一行或者同一列。现在小凸想知道，选出的 $n$ 个数中第 $k$ 大的数的最小值是多少。

输入输出格式

输入格式：

第 $1$ 行读入 $3$ 个整数 $n,m,k$ 。

接下来 $n$ 行，每一行有 $m$ 个数字，第 $i$ 行第 $j$ 个数字代表矩阵中第 $i$ 行第 $j$ 列的元素 A_{i,j}Ai,j​ 。

输出格式：

输出包含一行，为选出的 $n$ 个数中第 $k$ 大数的最小值。

说明

对于 $20$ % 的数据， $1\le n\le m\le 9$

对于 $40$ % 的数据， $1\le n\le m\le 22,1\le n\le 12$

对于 $100$ % 的数据， 1 \leq k \leq n \leq m \leq 250, 1 \leq A_{i,j} \leq 10^91≤k≤n≤m≤250,1≤Ai,j​≤109

 

题意：很清楚；

题解：

①二分第k大的数的最小值，如果a i,j<=mid 行i向列j连边，最后对行列二分图匹配，如果匹配数>=n-k+1向左二分，反之向左；

②说下证明（%%%）：有一个事实是对于二分图匹配>=n-k+1成立的答案mid是连续的（具有二分性的），假设最后二分出来的为ans，1~ ans-1显然不行(因为小于等于ans的凑不够n-k+1个)，ans+1~max可能不行(因为可能大于等于ans的凑不够k个)；所以ans就一定行吗？是的，因为由二分的定义可知，在ans选取的时候，一定会有n-k+1个小于等于ans的值，一定不会有n-k+1个小于ans的值（否则应该是ans-1）,则一定会有k+1个大于等于ans的值。

自然ans就是第k大了。得到存在性和最优性后，二分是安全舒适的；

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int N=251; 6 int n,m,k,mx,p[N<<1],b[N<<1],hd[N<<1],o,a[N][N]; 7 struct Edge{
   int v,nt;}E[N*N]; 8 char gc(){ 9     static char *p1,*p2,s[1000000];10     if(p1==p2) p2=(p1=s)+fread(s,1,1000000,stdin);11     return (p1==p2)?EOF:*p1++;12 }13 int rd(){14     int x=0; char c=gc();15     while(c<'0'||c>'9') c=gc();16     while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=gc();17     return x;18 }19 void adde(int u,int v){20     E[o] = (Edge){v,hd[u]}; hd[u] = o++;21     E[o] = (Edge){u,hd[v]}; hd[v] = o++;22 }23 bool match(int u){24     for(int i=hd[u],v;i!=-1;i=E[i].nt){25         if(b[v=E[i].v]) continue; b[v]=1;26         if(!p[v]||match(p[v])) {27             p[v]=u,p[u]=v;28             return true;29         }30     }31     return false;32 }33 bool check(int mid){34     memset(hd,-1,sizeof(hd)); o=0;35     memset(p,0,sizeof(p));36     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]<=mid) adde(i,j+n);37     int ans = 0;38     for(int i=1;i<=n;i++){39         memset(b,0,sizeof(b));40         if(!p[i]&&match(i)) ans++;41     }42     return ans>=n-k+1;43 }44 int main()45 {    freopen("bzoj4443.in","r",stdin);46     freopen("bzoj4443.out","w",stdout);47     n=rd(); m=rd(); k=rd();48     for(int i=1;i<=n;i++)49     for(int j=1;j<=m;j++) 50     mx = max(a[i][j]=rd(),mx);51     int l=1,r=mx;52     while(l
        
         >1;54         if(check(mid)) r=mid;55         else l=mid+1;56     }57     printf("%d\n",l);58     return 0;59 }//by tkys_Austin;