题目链接

二分+最大check

 #include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define rre(i,r,l) for(int i=(r);i>=(l);i--)
#define re(i,l,r) for(int i=(l);i<=(r);i++)
#define Clear(a,b) memset(a,b,sizeof(a))
#define inout(x) printf("%d",(x))
#define douin(x) scanf("%lf",&x)
#define strin(x) scanf("%s",(x))
#define LLin(x) scanf("%lld",&x)
#define op operator
#define CSC main
typedef unsigned long long ULL;
typedef const int cint;
typedef long long LL;
using namespace std;
void inin(int &ret)
{
ret=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}
while(ch>=''&&ch<='')ret*=,ret+=ch-'',ch=getchar();
ret=f?-ret:ret;
}
int n,m,k,a[][],Max,s,t,ed;
int head[],next[],zhi[],cap[];
void add(int a,int b,int c)
{
next[++ed]=head[a],head[a]=ed,zhi[ed]=b,cap[ed]=c;
next[++ed]=head[b],head[b]=ed,zhi[ed]=a,cap[ed]=;
}
queue<int>h;int dis[];
bool bfs()
{
Clear(dis,);
dis[s]=;h.push(s);
while(!h.empty())
{
int x=h.front();h.pop();
for(int i=head[x];i;i=next[i])if(cap[i]&&!dis[zhi[i]])
dis[zhi[i]]=dis[x]+,h.push(zhi[i]);
}
return dis[t];
}
int dfs(int x,int Max)
{
if(!Max||x==t)return Max;
int ret=,temp;
for(int i=head[x];i;i=next[i])if(cap[i]&&dis[zhi[i]]==dis[x]+)
{
temp=dfs(zhi[i],min(Max,cap[i]));
ret+=temp,Max-=temp;
cap[i]-=temp,cap[i^]+=temp;
if(!Max)return ret;
}
if(!ret)dis[x]=-;
return ret;
}
int dinic()
{
int ret=;
while(bfs())ret+=dfs(s,);
return ret;
}
bool check(int x)
{
Clear(head,);ed=;
re(i,,n)re(j,,m)
if(a[i][j]<=x)add(i,j+n,);
re(i,,n)add(s,i,);
re(i,,m)add(i+n,t,);
int ret=dinic();
if(ret>=n-k+)return ;
return ;
}
int main()
{
inin(n),inin(m),inin(k);s=n+m+,t=s+;
re(i,,n)re(j,,m)inin(a[i][j]),Max=max(Max,a[i][j]);
int l=,r=Max,mid,ans;
while(l<=r)
{
mid=(l+r)>>;
if(check(mid))ans=mid,r=mid-;
else l=mid+;
}
printf("%d",ans);
return ;
}

最新文章

  1. apk安全测试思路
  2. Java的List排序
  3. Android实现apk文件下载并自动安装
  4. C 文件读写2
  5. 手机端Post 数据
  6. DEDECMS中,文章页直接输出字段名
  7. 关于GestureDetector.OnGestureListener的onScroll参数distance问题
  8. linux系统编程快速定位头文件的技巧之强大的grep命令
  9. Jenkins + Docker 持续集成
  10. 为什么我的gridview.DataKeys.count总是为零?并提示索引超出范围
  11. InnoDB 存储引擎的特点及优化方法
  12. java.lang.OutOfMemoryError:GC overhead limit exceeded解决方法
  13. C盘清理(安装Visual Studio 或者Office后)
  14. ABP框架系列之二十二:(Dynamic-Web-API-动态WebApi)
  15. JMeter&#160;利用Jmeter批量数据库插入数据
  16. dijksta 模板
  17. Flume数据采集准备
  18. Mac中opencv批量对图片进行二值化
  19. 纯CSS3实现打火机火焰动画
  20. ubuntu 下关闭apache服务自动启动

热门文章

  1. laravel项目thinksns+安装pc前端页面
  2. ros 运行rviz时出现 QXcbConnection: XCB error: 148 错误 解决方法
  3. what&#39;s the python之内置函数
  4. what&#39;s the python之python介绍
  5. 安装setuptools
  6. 小睿开始呼叫用户,然后FS怎么跟用户交互的整个流程原理
  7. sap 申请 新系统用户
  8. Scala中 =&gt; Unit 与 () =&gt;Unit的区别
  9. Windows本机搭建Redis
  10. Py中的矩阵乘法【转载】