90分 WA#1 求助
查看原帖
90分 WA#1 求助
187232
Logic_J_X楼主2023/9/11 21:48

手捏了好几个数据都 hack 不掉我的程序,第一个点到底是什么数据......

#include<bits/stdc++.h>
#define N 3005
#define M 400005
#define inf 0x3f3f3f3f
#define II inline int 
#define IV inline void
#define re read() 
#define pf printf
#define gc getchar()
#define pfi(x) printf("%d\n",x)
#define cmx(x,y) x=max(x,y)
#define clr(a,n) memset(a,0,sizeof(int)*(n)) 
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define f(i,x,y) for(int i=(x); i<=(y); i++)
#define fe(i,v,u) for(int i=head[u],v=e[i].v; i; i=e[i].nex,v=e[i].v)
using namespace std;
II read(){
	int res=0; char c=gc;
	while(c<48 || 57<c) c=gc;
	while(47<c && c<58) res=(res<<1)+(res<<3)+(c^48),c=gc;
	return res;
}
int n0,n1,m,s,t,ans;
int a[N],b[N];
struct edge{
	int v,w,nex;
}e[N*N<<1];
int sav[N],head[N],now[N],cnt;
IV adde(int u,int v,int w){
	e[++cnt]={v,w,head[u]}; head[u]=cnt;
	e[++cnt]={u,0,head[v]}; head[v]=cnt;
}
queue<int>q;
int d[N];
bool bfs(){
	clr(d,t+1);
	while(!q.empty()) q.pop();
	q.push(s); d[s]=1; now[s]=head[s];
	int u;
	while(!q.empty()){
		u=q.front(); q.pop();
		fe(i,v,u)
			if(e[i].w && !d[v]){
				q.push(v);
				now[v]=head[v];
				d[v]=d[u]+1;
				if(v==t) return 1;
			}
	}
	return 0;
}
II dinic(int u,int fl){
	if(u==t) return fl;
	int res=fl,k,i,v;
	for(i=now[u]; i; i=e[i].nex)
		if(e[i].w && d[u]+1==d[v=e[i].v]){
			k=dinic(v,min(res,e[i].w));
			if(!k) d[v]=0;
			e[i].w-=k; e[i^1].w+=k;
			res-=k;
			if(res==0) break;
		}
	now[u]=i;
	return fl-res;
}
int in[N];
vector<int>ev[N];
int pc[N][N];
II calc(int x,int y){
	clr(in,t+1); clr(head,t+1); cnt=1;
	int o=(x>0)+(y>0),tot=0;
	for(int v:ev[x]) in[v]++;
	for(int v:ev[y]) in[v]++;
	f(i,1,n1) if(in[i]==o){
		tot++;
		if(b[i]&1){
			adde(s,i,1);
			f(j,1,n1) if(in[j]==o && !(b[j]&1) && !(pc[i][j]&1)) adde(i,j,1);	
		}
		else adde(i,t,1);	
	}
	int res=0;
	while(bfs()) res+=dinic(s,inf);
	return o+tot-res;
}
IV sol(){
	s=n1+1; t=s+1;
	f(i,1,n1)
		f(j,1,n1) pc[i][j]=__builtin_popcount(b[i]|b[j]);
	cmx(ans,calc(0,0));
	f(i,0,n0)
		f(j,i+1,n0) cmx(ans,calc(i,j));
	pfi(ans);
}
signed main(){
	int T=re;
	while(T--){
		n0=re; n1=re; m=re;
		ans=0;
		f(i,1,n0) ev[i].clear();
		f(i,1,n0) a[i]=re;
		f(i,1,n1) b[i]=re;
		int u,v;
		f(i,1,m) u=re,v=re,ev[u].push_back(v); 
		sol();
	}
	return 0;
}
2023/9/11 21:48
加载中...