HDU - 2018杭電ACM集訓隊單人排位賽 - 3 - Problem B. Bullet

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

題目大意：每行每列最多取一個數，構成的集合在滿足元素數量最多的前提下，最小值最大。 最小值增大時，可比對邊的數量減少，是以最大比對可能減小，于是可以二分最小值，每次求圖中權值大于最小值的邊的最大比對。

#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;
}