Problem B.Bullet
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 73 Accepted Submission(s): 36
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×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 n（n≤500）
Then n lines follow. In each line there are n integers, and Aij represents the experience of the monster at grid (i,j). If Aij=0, there is no monster at grid (i,j).（Aij≤1e9）
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
题目大意：每行每列最多取一个数，构成的集合在满足元素数量最多的前提下，最小值最大。 最小值增大时，可匹配边的数量减少，所以最大匹配可能减小，于是可以二分最小值，每次求图中权值大于最小值的边的最大匹配。
解题思路：二分图最大匹配 + Hungarian 算法。
AC 代码
/
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=510; struct edge { int to,nx,w; }eds[maxn*maxn]; int n, cnt; int linker[maxn], vis[maxn], head[maxn]; void init() { cnt=0; mem(head,-1); } void addEdge(int u, int v, int w) { eds[cnt].to=v; eds[cnt].w=w; eds[cnt].nx=head[u]; head[u]=cnt++; } bool dfs(int u,int limit) { int v; for(int i=head[u];i!=-1;i=eds[i].nx) { v=eds[i].to; if(eds[i].w>=limit && !vis[v]) { vis[v]=1; if(!linker[v]||dfs(linker[v],limit)) { linker[v]=u; return 1; } } } return 0; } int jde(int limit) { mem(linker,0); cnt=0; for(int i=0;i<n;i++) { mem(vis,0); if(dfs(i,limit)) cnt++; } return cnt; } int main() { while(~scanf("%d",&n)) { init(); int w; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { scanf("%d",&w); addEdge(i,j,w); } int ans=jde(1); // 求出最大匹配数 int l=0,r=INT_MAX; while(r>=1) // 二分思想，可自己模拟下就明白了 { if(jde(l+r)==ans) l+=r; else r>>=1; } printf("%d\n",max(1,l)); } return 0; }
