#2006. 「SCOI2015」小凸玩矩阵

题目描述

小凸和小方是好朋友，小方给小凸一个 N×M N \times MN×M（N≤M N \leq MN≤M）的矩阵 A AA，要求小凸从其中选出 N NN 个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的 N NN 个数中第 K KK 大的数字的最小值是多少。

输入格式

第一行给出三个整数 N NN、M MM、K KK。
接下来 N NN 行，每行 M MM 个数字，用来描述这个矩阵。

输出格式

输出选出来的 N NN 个数中第 K KK 大的数字的最小值。

样例

样例输入

样例输出

数据范围与提示

1≤K≤N≤M≤250,1≤Ai,j≤109 1 \leq K \leq N \leq M \leq 250, 1 \leq A_{i, j} \leq 10 ^ 91≤K≤N≤M≤250,1≤Ai,j≤109

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,k,map[][],a[],b[],ans=0x3f3f3f3f;

bool vis[];

int cmp(int x,int y){return x>y;}

void check(){

    for(int i=;i<=n;i++)b[i]=a[i];

    sort(b+,b+n+,cmp);

    ans=min(ans,b[k]);

}

void dfs(int now){

    if(now==n+){

        check();

        return;

    }

    for(int i=;i<=m;i++){

        if(!vis[i]){

            vis[i]=;

            a[now]=map[now][i];

            dfs(now+);

            vis[i]=;

        }

    }

}

int main(){

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

    int x;

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

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

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

    dfs();

    printf("%d",ans);

}

20分暴力

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 510

#define INF 1000000000

using namespace std;

int S,T,num=,head[maxn],n,m,k,dis[maxn],a[maxn][maxn];

struct node{int to,pre,v;}e[maxn*maxn];

void Insert(int from,int to,int v){

    e[++num].to=to;e[num].v=v;e[num].pre=head[from];head[from]=num;

    e[++num].to=from;e[num].v=;e[num].pre=head[to];head[to]=num;

}

int dinic(int x,int flow){

    if(x==T||flow==)return flow;

    int rest=flow;

    for(int i=head[x];i;i=e[i].pre){

        int to=e[i].to;

        if(dis[to]==dis[x]+&&e[i].v>){

            int delta=dinic(to,min(e[i].v,rest));

            e[i].v-=delta;

            e[i^].v+=delta;

            rest-=delta;

        }

    }

    return flow-rest;

}

bool spfa(){

    memset(dis,-,sizeof(dis));

    queue<int>q;q.push(S);dis[S]=;

    while(!q.empty()){

        int now=q.front();q.pop();

        for(int i=head[now];i;i=e[i].pre){

            int to=e[i].to;

            if(dis[to]==-&&e[i].v>){

                dis[to]=dis[now]+;

                if(to==T)return ;

                q.push(to);

            }

        }

    }

    return dis[T]!=-;

}

int work(){

    int res=;

    while(spfa()){

        res+=dinic(S,INF);

    }

    return res;

}

bool check(int x){

    memset(head,,sizeof(head));num=;

    for(int i=;i<=n;i++)Insert(S,i,);

    for(int i=;i<=m;i++)Insert(i+n,T,);

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

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

            if(a[i][j]<=x)Insert(i,j+n,);

    int res=work();

    if(res>=n-k+)return ;

    return ;

}

int main(){

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

    S=;T=n+m+;

    int mx=;

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

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

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

            mx=max(mx,a[i][j]);

        }

    int l=,r=mx,ans=;

    while(l<=r){

        int mid=(l+r)>>;

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

        else l=mid+;

    }

    printf("%d",ans);

}

100分二分答案+网络流

巴特西

loj #2006. 「SCOI2015」小凸玩矩阵