找不同大赛
查看原帖
找不同大赛
800499
suzhikz楼主2024/11/9 00:10

改的快和第一篇一样了,怎么还是错的

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
#define int long long
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
//void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=3305;
int t; 
int n,m,nm;
int a[N],b[N];
bool e[N+N][N+N];
vector<int>g[N];
int vis[N],num,flag[N],tot;
int p[N];
bool match(int x){
	for(int i:g[x]){
		if(vis[i]!=num&&flag[i]==tot){
			vis[i]=num;
			if(!p[i]||match(p[i])){
				p[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
signed main(){
	read(t);
	read(n);read(m);read(nm);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=m;i++)read(b[i]);
	for(int i=1;i<=m;i++){
		if(b[i]&1)
		for(int j=i+1;j<=m;j++){
//			cout<<i<<' '<<j<<"abs"<<endl;
//			cout<<(b[i]^b[j])%2<<' '<<(__builtin_popcount((b[i]|b[j]))&1)<<endl;
			if((b[j]&1)==0&&((__builtin_popcount((b[i]|b[j])))&1)==0){
//				cout<<i<<"->"<<j<<endl;
				g[i].push_back(j);
			}
		} 
	}
	for(int u,v,i=1;i<=nm;i++){
		read(u);read(v);
		e[u][v+N]=e[v+N][u]=1;
	}
	int ans=0;int maxx=0;
	for(int i=1;i<=m;i++){
		if(b[i]&1){
			num++;
			ans+=match(i);
		}
	}
	maxx=m-ans;
	
	for(int i=1;i<=n;i++){
		memset(p,0,sizeof(p));
		tot++;
		int ch=0;
		ans=0;
		for(int j=1;j<=m;j++){
			if(e[i][j+N]){
				flag[j]=tot;
				ch++;
			}
		}
		for(int j=1;j<=m;j++){
			if(flag[j]==tot&&(b[j]&1)){
				num++;
				ans+=match(j);
			}
		}
		maxx=max(maxx,1+ch-ans);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(((a[i]^a[j])&1)==0)continue;
			tot++;
			memset(p,0,sizeof(p));
			int ch=0;
			ans=0;
			for(int k=1;k<=m;k++){
				if(e[i][k+N]&&e[j][k+N]){
					flag[k]=tot;ch++;
				}
			}
			for(int k=1;k<=m;k++){
				if(flag[k]==tot&&(b[k]&1)){
					num++;
					ans+=match(k); 
				}
			}
			maxx=max(maxx,2+ch-ans);
//			cout<<2+ch-ans<<endl;
		}
	}
	cout<<maxx;
	return 0;
}

2024/11/9 00:10
加载中...