链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4443
数据生成器：http://paste.ubuntu.com/23621596/
神犇题解：http://krydom.com/bzoj4443/
题解
考虑最值的话，肯定想到二分
又因为每行/每列只能选一个
那就是二分图匹配辣！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 500 + 9;
const int M = 500000;
const int INF = 1e9;
int head[N],to[M],nxt[M],flow[M],cur[N],dis[N],TT;
int n,m,K,S,T,val[N/2][N/2],tot,TMP[M];
queue<int> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void Add_Edge(int u, int v) {
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = 1;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}
inline bool BFS() {
memset(dis,60,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + 1 && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < 1e8;
}
int DFS(int w, int v) {
if (w == T) {
return v;
} else {
int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
int tmp = DFS(to[i], min(v, flow[i]));
v -= tmp; ret += tmp;
flow[i] -= tmp; flow[i^1] += tmp;
if (!v) break;
}
}
return ret;
}
}
inline int Dinic() {
int ret = 0;
while (BFS()) {
memcpy(cur,head,sizeof(head));
ret += DFS(S,INF);
}
return ret;
}
inline bool judge(int sta) {
memset(head,0,sizeof(head));
TT = 1; S = 0; T = N - 1;
for (int i=1;i<=n;i++) {
Add_Edge(S,i);
for (int j=1;j<=m;j++) {
if (val[i][j] <= sta) {
Add_Edge(i,n+j);
}
}
}
for (int i=1;i<=m;i++)
Add_Edge(n+i,T);
return Dinic() >= n - K + 1;
}
int main(){
n = read(); m = read(); K = read();
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
val[i][j] = TMP[++tot] = read();
}
}
sort(TMP+1, TMP+1+tot);
tot = unique(TMP+1, TMP+1+tot) - TMP - 1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
val[i][j] = lower_bound(TMP+1, TMP+1+tot, val[i][j]) - TMP;
}
}
int l=1, r=tot, mid, vout=0;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) r = mid-1, vout = mid;
else l = mid + 1;
}
printf("%d\n",TMP[vout]);
return 0;
}
Great blog here! Also your web site loads up very fast!
What host are you using? Can I get your affiliate link to your
host? I wish my website loaded up as quickly as yours lol
Simply desire to say your article is as astonishing.
The clarity for your put up is simply great and i could
suppose you’re a professional in this subject.
Fine with your permission let me to take hold of your feed to stay updated
with approaching post. Thank you 1,000,000 and please carry
on the enjoyable work.
Good article. I am going through many of these issues as well..
Hi there! This is my first visit to your blog!
We are a group of volunteers and starting a new
initiative in a community in the same niche. Your blog provided us beneficial information to work on. You have done a marvellous job!
This post is in fact a good one it assists new net visitors, who are wishing for blogging.
Hi, i think that i saw you visited my website thus i came
to “return the favor”.I’m trying to find things to improve my website!I suppose its ok to use some of your ideas!!
Good post. I learn something new and challenging on websites
I stumbleupon on a daily basis. It will always be helpful to
read articles from other authors and use a
little something from their sites.
Spot on with this write-up, I truly believe this site needs a lot more attention. I’ll probably
be back again to read through more, thanks for the info!
It’s genuinely very complicated in this full of activity life to listen news on Television, so I only use
world wide web for that reason, and take the most up-to-date news.
This design is spectacular! You obviously know how to keep
a reader amused. Between your wit and your videos, I was almost moved to start my own blog (well,
almost…HaHa!) Fantastic job. I really enjoyed what you had to say, and
more than that, how you presented it. Too cool!
Hey there! This post couldn’t be written any
better! Reading through this post reminds me of my previous room mate!
He always kept chatting about this. I will forward this write-up to him.
Pretty sure he will have a good read. Thanks for sharing!
I blog frequently and I really thank you for your information. The article has really peaked my interest.
I will book mark your site and keep checking
for new details about once a week. I opted in for your Feed too.
We’re a group of volunteers and starting a brand new scheme in our community.
Your site offered us with useful information to work on.
You have done a formidable job and our entire neighborhood will probably be grateful to
you.
It’s amazing in support of me to have a site, which is helpful for my know-how.
thanks admin
My coder is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the expenses.
But he’s tryiong none the less. I’ve been using Movable-type on a variety of websites
for about a year and am concerned about switching to another platform.
I have heard fantastic things about blogengine.net.
Is there a way I can import all my wordpress content into it?
Any help would be really appreciated!
Awesome post.
Good day! I could have sworn I’ve been to this site before but after going through many
of the posts I realized it’s new to me. Regardless, I’m certainly pleased I
found it and I’ll be bookmarking it and checking back often!
Definitely believe that which you said. Your favorite reason seemed to be on the web the easiest thing to be aware of.
I say to you, I certainly get irked while people think about worries that they plainly don’t know about.
You managed to hit the nail upon the top as well as defined out the whole thing without having side-effects , people can take a signal.
Will probably be back to get more. Thanks
Awesome article.
you’re actually a good webmaster. The web site loading velocity is amazing.
It kind of feels that you’re doing any distinctive trick.
Furthermore, The contents are masterpiece. you have done a fantastic job on this subject!
You actually make it appear so easy with your presentation however I find this matter to be actually something which I believe I might by no means understand. It sort of feels too complex and extremely vast for me. I’m having a look ahead for your next publish, I will try to get the dangle of it!