C++14(g++5.4) 解法, 执行用时: 286ms, 内存消耗: 26856K, 提交时间: 2020-04-19 19:06:30

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const ll inf = 2147483647;
const ll N = 1e5 + 5;
const ll M = 5e5 + 5;
struct E{
    ll to, next, w;
}e[M * 2];
ll head[N], cur[N], dep[N];
ll cnt, n, m, s, t,x,y,a[300][300],k;
void init()
{
	cnt=1;
	n=m=s=t=0;
	memset(head,0,sizeof(head));
	memset(cur,0,sizeof(cur));
	memset(dep,0,sizeof(dep));
	memset(e,0,sizeof(e));
}
void ae(ll x, ll y, ll z){
    e[++cnt] = (E){ y, head[x], z }, head[x] = cnt;
    e[++cnt] = (E){ x, head[y], 0 }, head[y] = cnt;
}
queue<ll> q;
bool bfs()
{
    memset(dep, 0, sizeof(dep));
    while( !q.empty() ) q.pop();
    dep[s] = 1, q.push(s);
    while( !q.empty() ){
        ll u = q.front(); q.pop();
        for( ll i = head[u]; i; i = e[i].next )
        {
            ll v = e[i].to;
            if( !dep[v] && e[i].w > 0 )
                dep[v] = dep[u] + 1, q.push(v);
        }
    }
    return dep[t] != 0;
}
ll dfs(ll x, ll dist)
{
    if( x == t ) return dist;
    ll flow = 0;
    for( ll &i = cur[x]; i; i = e[i].next ) {
        ll v = e[i].to;
        if( dep[v] == dep[x] + 1 && e[i].w > 0 ) {
            ll di = dfs(v, min(e[i].w, dist));
            if( di > 0 )
            {
                e[i].w -= di, e[ i ^ 1 ].w += di;
                dist -= di, flow += di;
                if( dist == 0 ) return flow; 
            }
        } 
    }
    return flow;
}
ll mxfl()
{
    ll ans = 0;
    while( bfs() )
    {
        memcpy( cur, head, sizeof(cur) );
        ll di = 1;
        while( di  = dfs(s, inf) )  ans += di;
    }
    return ans;
}
int get(int nn)
{
	init();
	n=x+y+1;
	s=x+y+1;
	t=x+y+2;
	for (int i=1;i<=x;i++)
		for (int ii=1;ii<=y;ii++)
			if (a[i][ii]<=nn)
				ae(i,x+ii,1);
	for (int i=1;i<=x;i++)
		ae(x+y+1,i,1);
	for (int i=1;i<=y;i++)
		ae(x+i,x+y+2,1);
//	cout<<n<<' '<<m<<' '<<s<<' '<<t<<endl;
//	cout<<s<<"-->"<<t<<endl;
	int u;
//	cout<<nn<<' '<<(u=abb())<<endl;
	u=mxfl();
//	cout<<u<<'-';
	return u<=x-k;
}
int fd(int l,int r)
{
	if (l>=r) return r;
	int mid=(l+r)/2;
//	cout<<mid<<endl;
	if (get(mid+1))
		return fd(mid+1,r);
	else return fd(l,mid);
}
int main()
{
	cin>>x>>y>>k;
	for (int i=1;i<=x;i++)
		for (int ii=1;ii<=y;ii++)
			cin>>a[i][ii];
//	for (int i=1;i<=10;i++)
//		cout<<get(i)<<endl;
	cout<<fd(0,int(1e9))+1;
 } 

C++(clang++ 11.0.1) 解法, 执行用时: 179ms, 内存消耗: 1416K, 提交时间: 2022-11-25 11:27:49

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define RG register;
#define MAX 500
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,m,g[MAX][MAX],K;
struct Line{int v,next;}e[MAX*MAX];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
void Build(int Mid)
{
    memset(h,0,sizeof(h));cnt=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(g[i][j]<=Mid)Add(i,j);
}
int match[MAX],vis[MAX],tot;
bool dfs(int u)
{
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].v;
        if(vis[v]==tot)continue;
        vis[v]=tot;
        if(!match[v]||dfs(match[v])){match[v]=u;return true;}
    }
    return false;}
int check()
{
    memset(match,0,sizeof(match));
    int ret=0;
    for(int i=1;i<=n;++i){
        ++tot;
        if(dfs(i))++ret;}
    return ret;
}
int main()
{
    n=read();m=read();K=n-read()+1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)g[i][j]=read();
    int l=0,r=1e9,ans=1e9;
    while(l<=r){
        int mid=(l+r)>>1;
        Build(mid);
        if(check()>=K)ans=mid,r=mid-1;
        else l=mid+1;}
    printf("%d\n",ans);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 88ms, 内存消耗: 760K, 提交时间: 2022-11-26 18:06:57

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<vector<int>> ma;
vector<int> vis, mat;

int dfs(int u, int ans, int tot)
{
    for(int i = 0; i < m; i ++ ) {
        if(ma[u][i] <= ans && vis[i] != tot) {
            vis[i] = tot;
            if(!mat[i] || dfs(mat[i] - 1, ans, tot)) {
                mat[i] = u + 1;
                return 1;
            }
        }
    }
    return 0;
}
bool check(int ans)
{
    vis = mat = vector<int> (m);
    int tot = 0, sum = 0;
    for(int i = 0; i < n; i ++ ) {
        sum += dfs(i, ans, ++ tot);
    }
    return sum >= k;
}
int main()
{
    cin >> n >> m >> k;
    k = n - k + 1;
    int l = 2e9, r = 0;
    ma = vector<vector<int> > (n, vector<int> (m) );
    for(int i = 0; i < n; i ++ ) {
        for(int j = 0; j < m; j ++ ) {
            cin >> ma[i][j];
            l = min(l, ma[i][j]);
            r = max(r, ma[i][j]);
        }
    }
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid))    r = mid - 1;
        else    l = mid + 1;
    }
    cout << l << endl;
    return 0;
}