蒟蒻求助
查看原帖
蒟蒻求助
332686
liu_yi_tong楼主2020/8/9 20:32

求助: 这道题我的代码开了O2就RE或者T, 不开O2就都能A,这是为什么呢

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+190;
int a[maxn][maxn];
int n,m,k;
int vis[maxn],pipei[maxn];
struct E{
	int to,next;
}edge[maxn*2];
int head[maxn],tot;
void add(int from,int to){
	edge[++tot].to=to;
	edge[tot].next=head[from];
	head[from]=tot;
}
void build(int mid){
	memset(head,0,sizeof(head));tot=0;
	memset(pipei,0,sizeof(pipei));memset(edge,0,sizeof(edge));
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=m;j++){
			if(a[i][j]>mid)continue;
			add(i,j);
			//add(j,i);
		}
	}
}
bool Find(long long u){
	for(register int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		//printf("%lld %lld\n",edge);
		if(!vis[v]){
			vis[v]=1;
			if(!pipei[v]||Find(pipei[v])){
				pipei[v]=u;
				return true;
			}
		}
	}
	return false;
}
bool check(int mid){
	int ans=0;
	for(register int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(Find(i))ans++;
	}
	//printf("%lld %lld\n",mid,ans);
	if(ans>=n-k+1)return true;
	else return false;
}
inline int read()
{
	char c=getchar();
	int  f=1,x=0;
	for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return f*x;
}
int main(){
	int Max=0,Min=1e9+10;
	n=read();m=read();k=read();
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=m;j++){
			a[i][j]=read();
			Max=max(Max,a[i][j]);
			Min=min(Min,a[i][j]);
		}
	}
	int l=Min,r=Max,ans;
	while(l<=r){
		//printf("%lld %lld ",l,r);
		int mid=l+r>>1;
		//memset(pipei,0,sizeof(pipei));
		build(mid);
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	printf("%d",l);
	return 0;
}

2020/8/9 20:32
加载中...