zoj 3760 Treasure Hunting 最大独立集 - c++编程基础

首先根据x^y的奇偶将图分成X，Y集合，然后若对任意 x,y ，不满足gcd的条件，既连边，求最大独立集即可【最大独立集=总权值-最小点覆盖(最大流，最小割)】。

为什么可以这样分成二分图，因为奇数和奇数，或者偶数和偶数异或的时候，二进制第一位一定是0，也就是一定是偶数，题目告诉了我们P一定是偶数，所以它们和P一定至少有一个公约数2，所以它们一定没有边（我们是以不满足条件建边的）。

最大独立集的概念就是，选出权值最大的点，使他们两两都没有边相连。

具体的建图代码就是常规的二分图。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #define eps 1e-12 #define INF 0x7fffffff #define maxn 4222 using namespace std; int n,m; int en; int st,ed; //源点和汇点 int dis[maxn] ;//dis[i],表示 到 原点 s 的 层数 int que[999999]; struct edge { int to,c,next; }; edge e[999999]; int head[maxn]; void add(int a,int b,int c) { e[en].to=b; e[en].c=c; e[en].next=head[a]; head[a]=en++; e[en].to=a; e[en].c=0; e[en].next=head[b]; head[b]=en++; } int bfs() { memset(dis,-1,sizeof(dis)); dis[st]=0; int front=0,rear=0; que[rear++]=st; while(front