时间限制: 6 Sec 内存限制: 128 MB
题目描述
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.
输入
The first line contains an integer n
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).
输出
One integer, the value of max experience.
样例输入
2
2 0
1 8
样例输出
2

每行每列最多取一个数，构成的集合在满足元素数量最多的前提下，最小值最大。
最小值增大时，可匹配边的数量减少，所以最大匹配可能减小，于是可以二分最小值，每次求图中权值大于最小值的边的最大匹配。

#define IN_LB() freopen("C:\\Users\\acm2018\\Desktop\\in.txt","r",stdin)

#define OUT_LB() freopen("C:\\Users\\acm2018\\Desktop\\out.txt","w",stdout)

#define IN_PC() freopen("C:\\Users\\hz\\Desktop\\in.txt","r",stdin)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 505;

struct edge {

    int v,w,nex;

} ed[maxn*maxn];

int head[maxn],cnt,n,vis[maxn],match[maxn];

void addedge(int u,int v,int w) {

    cnt++;

    ed[cnt].v = v;

    ed[cnt].w = w;

    ed[cnt].nex = head[u];

    head[u] = cnt;

}

bool dfs(int u,int limit) {

    for(int i=head[u]; i; i=ed[i].nex) {

        int v = ed[i].v;

        if(ed[i].w>=limit&&!vis[v]) {

            vis[v] = 1;

            if(!match[v]||dfs(match[v],limit)) {

                match[v] = u;

                return true;

            }

        }

    }

    return false;

}

int judge(int limit) {

    memset(match,0,sizeof match);

    int cnt = 0;

    for(int i=1; i<=n; i++) {

        memset(vis,0,sizeof vis);

        if(dfs(i,limit))

            cnt++;

    }

    return cnt;

}

int main() {

//    IN_LB();

    scanf("%d",&n);

    for(int i=1; i<=n; i++) {

        for(int j=1; j<=n; j++) {

            int weight;

            scanf("%d",&weight);

            addedge(i,j,weight);

        }

    }

    int ans = judge(1);

    int res = 0,base = 1<<30;

    while(base>=1) {

        if(judge(res+base) == ans) {

            res += base;

        } else

            base >>= 1;

    }

    printf("%d\n",max(1,res));

    return 0;

}