BZOJ 4443: [Scoi2015]小凸玩矩阵 最大流

4443: [Scoi2015]小凸玩矩阵

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=4443

Description

小凸和小方是好朋友，小方给小凸一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的N个数中第K大的数字的最小值是多少。

Input

第一行给出三个整数N,M,K

接下来N行，每行M个数字，用来描述这个矩阵

Output

如题

Sample Input

3 4 2

1 5 6 6

8 3 4 3

6 8 6 3

Sample Output

3

Hint

题意

题解：

二分答案，然后判断是否最大流大于等于n-k+1就好了

这个模型还是比较显然的啦

代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1000000,MAXM=1000000,inf=1e9+500;

struct Edge

{

    int v,c,f,nx;

    Edge() {}

    Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}

} E[MAXM];

int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],sz;

void init()

{

    sz=0; memset(G,-1,sizeof(G));

}

void link(int u,int v,int c)

{

    E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;

    E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;

}

bool bfs(int S,int T)

{

    static int Q[MAXN]; memset(dis,-1,sizeof(dis));

    dis[S]=0; Q[0]=S;

    for (int h=0,t=1,u,v,it;h<t;++h)

    {

        for (u=Q[h],it=G[u];~it;it=E[it].nx)

        {

            if (dis[v=E[it].v]==-1&&E[it].c>E[it].f)

            {

                dis[v]=dis[u]+1; Q[t++]=v;

            }

        }

    }

    return dis[T]!=-1;

}

int dfs(int u,int T,int low)

{

    if (u==T) return low;

    int ret=0,tmp,v;

    for (int &it=cur[u];~it&&ret<low;it=E[it].nx)

    {

        if (dis[v=E[it].v]==dis[u]+1&&E[it].c>E[it].f)

        {

            if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))

            {

                ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp;

            }

        }

    }

    if (!ret) dis[u]=-1; return ret;

}

int dinic(int S,int T)

{

    int maxflow=0,tmp;

    while (bfs(S,T))

    {

        memcpy(cur,G,sizeof(G));

        while (tmp=dfs(S,T,inf)) maxflow+=tmp;

    }

    return maxflow;

}

int M[252][252];

int n,m,k;

int check(int x)

{

    init();

    int s = 0,t = n+m+1;

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

    {

        link(s,i,1);

        for(int j=1;j<=m;j++)

            if(M[i][j]<=x)

                link(i,n+j,1);

    }

    for(int j=1;j<=m;j++)

        link(n+j,t,1);

    int p=dinic(s,t);

    if(p>=n-k+1)return 1;

    return 0;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

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

        for(int j=1;j<=m;j++)

            scanf("%d",&M[i][j]);

    int l = 1,r = 1e9+1,ans = -1;

    while(l<=r)

    {

        int mid = (l+r)/2;

        if(check(mid))ans=mid,r=mid-1;

        else l=mid+1;

    }

    cout<<ans<<endl;

}