FJUT 毒瘤3（二分 + 最大匹配）题解

毒瘤3（二分 + 最大匹配）题解"/>

FJUT 毒瘤3（二分 + 最大匹配）题解

 

毒瘤3

TimeLimit:1000MS  MemoryLimit:256MB 64-bit integer IO format: %lld Problem Description

字节跳动有n款产品，和m  (m>=n)种不同的类型的客户。产品的价值由客户类型决定，第i种产品对于第j种个客户的价为值Aij．

形成一个n*m的价值矩阵。你需要为每款产品各选择一种要适应的客户。同时为最大化覆盖客户群体，且这些产品的适应客户

必须不同。问在为每个产品分配好客户类型后，把这些产品中价值第k大的数字最小能为多少。

 

Input

第一行给出三个整数N,M,K(1<=K<=N<=M<=250,1<=Aij<=1e9)

接下来N行，每行Ｍ个数字，用来描述每个产品对m种客户的价值

20%的数据n+m<=20

40%的数据n+m<=40

100%的数据n<=250

Output

输出价值第k大的数字的最小值

SampleInput

3 4 2
1 5 6 6 
8 3 4 3
6 8 6 3

SampleOutput

3

 

思路：显然肯定存在这个k，且肯定存在至少n - k + 1个匹配的权值比第k大的小。那么我们直接二分这个第k大的权值，然后把权值小于这个值的边建边跑最大匹配，如果至少有n - k + 1个匹配，那么显然这个值是可能的（不一定存在k-1个比他大）。根据题意第k大一定存在，那么最后二分出来的也一定存在。

代码：

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 300 + 10;
const int INF = 0x3f3f3f3f;
int linker[maxn];
bool used[maxn];
int n, m, k, cnt;
struct Edge{int to, next;int u, v, w;bool operator < (const Edge &x) const{return w < x.w;}
}edge[maxn * maxn], g[maxn * maxn];
int head[maxn], tot;
void addEdge(int u, int v){g[tot].to = v;g[tot].next = head[u];head[u] = tot++;
}
bool dfs(int u){for(int i = head[u]; i != -1; i = g[i].next){int v = g[i].to;if(!used[v]){used[v] = true;if(linker[v] == -1 || dfs(linker[v])){linker[v] = u;return true;}}}return false;
}
int hungry(){int res = 0;memset(linker, -1, sizeof(linker));for(int u = 1; u <= n; u++){memset(used, false, sizeof(used));if(dfs(u)) res++;}return res;
}
bool can(int mid){memset(head, -1, sizeof(head));tot = 0;for(int i = 1; i <= cnt; i++){if(edge[i].w <= mid){addEdge(edge[i].u, edge[i].v);}else break;}return (hungry() >= n - k + 1);
}
int main(){scanf("%d%d%d", &n, &m, &k);cnt = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &edge[++cnt].w);edge[cnt].u = i, edge[cnt].v = j;}}sort(edge + 1, edge + cnt + 1);int l = 1, r = 1e9, ans;while(l <= r){int mid = (l + r) >> 1;if(can(mid)){ans = mid;r = mid - 1;}else{l = mid + 1;}}printf("%d\n", ans);return 0;
}

 

转载于:.html