链接:
http://exam.upc.edu.cn/problem.php?id=4199
题目：
题目描述
NEUACM team holds summer training every year. This year n students participate in the training, and we provide m computers. Everyone has a suitability (0<=suitability<=1000) to every computer. Now our coach needs to draw up a plan, which satisfies: 1. every student uses one computer, and a computer can be used by no more than one student; 2. maximize the minimum suitability, which means if the answer is w, then everyone’s suitability to his computer shouldn’t be less than w.
Hint: huge input, please use fast IO.
输入
The first line contains n and m (1<=n<=m<=500), indicating the number of students and computers.
Next n lines describes every student’s suitability to every computer, number in ith line and jth row means student[i]’s suitability to computer[j].
输出
A single number w in one line, which is described before.
样例输入
1 2 1 10 2 3 10 1 2 2 1 1
样例输出
10 2
题意：
给你一个
n×m
的图mp，
mp[i][j]
代表第i个学生对第j台电脑的适配程度，每台电脑只能由一个人使用，问在所有人都有电脑用的情况下，所有人里对当前电脑的适配值的最小的那个人的适配值的最大值。
思路：
直接二分答案，也就是每个人可以成功适配的最小适配值，不断让这个值增大，直到无法完成二分图匹配。
实现：
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <list>
#include <iomanip>
#include <functional>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#define edl putchar('\n')
#define ll long long
#define clr(a,b) memset(a,b,sizeof a)
#define rep(i,m,n) for(int i=m ; i<=n ; i++)
#define fep(i,n) for(int i=0 ; i<n ; i++)
namespace FastIO {
const int SIZE =
1 <<
16;
char buf[SIZE], obuf[SIZE], str[
60];
int bi = SIZE, bn = SIZE, opt;
int read(
char *s) {
while (bn) {
for (; bi < bn && buf[bi] <=
' '; bi++);
if (bi < bn)
break;
bn = fread(buf,
1, SIZE, stdin);
bi =
0;
}
int sn =
0;
while (bn) {
for (; bi < bn && buf[bi] >
' '; bi++) s[sn++] = buf[bi];
if (bi < bn)
break;
bn = fread(buf,
1, SIZE, stdin);
bi =
0;
}
s[sn] =
0;
return sn;
}
bool read(
int& x) {
int n = read(str), bf;
if (!n)
return 0;
int i =
0;
if (str[i] ==
'-') bf = -
1, i++;
else bf =
1;
for (x =
0; i < n; i++) x = x *
10 + str[i] -
'0';
if (bf <
0) x = -x;
return 1;
}
};
#define read(x) FastIO::read(x)
using namespace std;
const int maxn =
1007;
int n, m, mp[maxn][maxn], link[maxn];
bool vis[maxn];
bool dfs(
int u,
int minn) {
fep(i,m) {
int v = i+n;
if(vis[v] || mp[u][v] < minn)
continue;
vis[v] =
true;
if(link[v] == -
1 || dfs(link[v], minn)) {
link[u] = v;
link[v] = u;
return true;
}
}
return false;
}
bool match(
int minn) {
clr(link, -
1);
int ans =
0;
fep(i,n)
if(link[i] == -
1) {
clr(vis,
0);
if(dfs(i, minn)) ans++;
}
return ans == n;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(
"../in.txt",
"r", stdin);
#endif
while(read(n)&&read(m)) {
fep(i,n) fep(j,m) read(mp[i][n+j]), mp[n+j][i] = mp[i][n+j];
int l=
0, r=
1000, mid, ans;
while(l<=r) {
mid = l+r>>
1;
if(match(mid)) {
ans = mid;
l = mid+
1;
}
else r = mid-
1;
}
printf(
"%d\n", ans);
}
return 0;
}
