题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2744
最大团是一个np问题。。
对于本题,做它的逆问题,建反图做最大独立集。
对于A最多取出两个点,枚举一下。
对于B,B是一个二分图。
注意用时间戳加快速度,还有就是注意一下取反的判定(||取反当然是&&
#include#include #include #include #define rep(i,l,r) for (int i=l;i<=r;i++)#define down(i,l,r) for (int i=l;i>=r;i--)#define clr(x,y) memset(x,y,sizeof(x))#define maxn 3005#define inf int(1e9)using namespace std;struct data{ int obj,pre;}e[maxn*maxn];int vis[maxn],head[maxn],a[maxn],b[maxn],mp[maxn][maxn],ban[maxn],mat[maxn],A,B,m,tot,t1,t2,ans;void insert(int x,int y){ e[++tot].obj=y; e[tot].pre=head[x]; head[x]=tot;}int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f;}bool count(int x){ int cnt=0; while (x){ x-=x&(-x); cnt++; } if ((cnt&1)==0) return 1; return 0;}bool dfs(int u){ if (ban[u]==t1) return 0; for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; if (ban[v]==t1||vis[v]==t2) continue; vis[v]=t2; if (mat[v]==0||dfs(mat[v])) {mat[v]=u; return 1;} } return 0;}int get(int x=0,int y=0){ clr(mat,0); t1++; int cnt=0; rep(i,1,B) if (mp[x][i]||mp[y][i]) ban[i]=t1,++cnt; rep(i,1,B){ ++t2; if (dfs(i)) cnt++; } return(B-cnt);}int main(){ A=read(); B=read(); m=read(); rep(i,1,A) a[i]=read(); rep(i,1,B) b[i]=read(); clr(mp,1); rep(i,1,m){ int x=read(),y=read(); mp[x][y]=0; } rep(i,1,B) mp[0][i]=0; rep(i,1,B) if (b[i]&1){ rep(j,1,B) if (!(b[j]&1)&&count(b[i]|b[j])) insert(i,j); } ans=get(); rep(i,1,A) ans=max(ans,get(i)+1); rep(i,1,A) if (a[i]&1) rep(j,1,A) if (!(a[j]&1)) ans=max(ans,get(i,j)+2); printf("%d\n",ans); return 0;}