【2018ACM山东省赛 - B】Bullet（二分 + 二分图匹配，匈牙利算法，卡常）
题干：
Problem Description
In GGO, a world dominated by gun and steel, players are fighting for the honor of being the strongest gunmen. Player Shino is a sniper, and her aimed shot kills one monster at a time. Now she is in an n×nn \times nn×n map, and there are monsters in some grids. Each monster has an experience. As a master, however, Shino has a strange self-restrain. She would kill at most one monster in a column, and also at most one in a row. Now she wants to know how to get max experience, under the premise of killing as many monsters as possible.
Input
The first line contains an integer nnn. (n<=500)
Then n lines follow. In each line there are n integers, and AijAijAij represents the experience of the monster at grid (i,j)(i,j)(i,j). If Aij=0Aij=0Aij=0, there is no monster at grid (i,j)(i,j)(i,j).
The experience is the minimal experience of all the monster which are killed.
It guaranteed that the maximum of the experience of the monster is not larger than 10^9
Output
One integer, the value of max experience.
Sample Input
2
2 0
1 8 Sample Output
2 题目大意：
就是一个打怪兽的游戏，你可以选择一个位置打怪兽，你可以打很多怪兽，但是每一行或者每一列最多打一个怪兽（和N皇后问题一样），每个位置上的怪兽都有一个权值（二维数组中的值），如果值为0代表这里没有怪兽，你打完怪兽可以获得的经验值为你所有打的怪兽的权值的最小值。问你最大可以获得多大的权值。
解题报告：
二分这个最小值，然后匈牙利check一下即可。
这题卡常（其实是复杂度本身就不允许），但是加了优化可以过。
优化1：memset改for（不过对这种单组样例的可能用处不大）
优化2：每次二分之后都新建边，这个对二分图的优化较大。
优化3：可以先离散化数据然后对数据二分，这样降低了二分次数（不过效果并不是很好，甚至500ms变成了900ms）
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 500 + 5;
struct Edge {
int to,ne,w;
} e[MAX*MAX];
int tot,head[MAX];
void add(int u,int v,int w) {
e[++tot].to = v;
e[tot].w = w;
e[tot].ne = head[u];
head[u] = tot;
}
int all,tmp,n,a[MAX][MAX];
int nxt[MAX];
bool use[MAX];
bool find(int x) {
for(int j = head[x]; ~j; j = e[j].ne) {
int v = e[j].to;
if(use[v] == 1) continue;
if(e[j].w < tmp) continue;
use[v]=1;
if(nxt[v] == 0 || find(nxt[v])) {
nxt[v] = x;
return 1;
}
}
return 0 ;
}
int match() {
// memset(nxt,0,sizeof nxt);
for(int i = 1; i<=n; i++) nxt[i] = 0;
int res = 0;
for(int i = 1; i<=n; i++) {
for(int i = 1; i<=n; i++) use[i] = 0;
if(find(i)) res++;
}
return res;
}
bool ok(int x) {
tmp = x;
if(match() == all) return 1;
else return 0 ;
}
int main()
{
tot=0;
int maxx=0;
cin>>n;
for(int i = 1; i<=n; i++) head[i] = -1;
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=n; j++) {
scanf("%d",&a[i][j]);maxx=max(maxx,a[i][j]);
}
}
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=n; j++) {
if(a[i][j]) add(i,j,a[i][j]);
}
}
all = match();
if(maxx == 0) {
printf("0\n");return 0 ;
}
int l = 1,r = maxx,mid,ans=0;
while(l<=r) {
mid=(l+r)>>1;
tot=0;
for(int i = 1; i<=n; i++) head[i] = -1;
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=n; j++) {
if(a[i][j] >= mid) add(i,j,a[i][j]);
}
}
if(ok(mid)) ans = mid,l = mid+1;
else r = mid-1;
}
printf("%d\n",ans);
return 0 ;
}
