链接
题目传送门: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; }