网站建设与管理专业就业方向,北京服装设计公司前十名,最好看的视频免费下载,黑龙江省建设网站首页题目链接#xff1a;bzoj2744 题目大意#xff1a; 两个国家看成是AB两国#xff0c;现在是两个国家的描述#xff1a; 1.A国#xff1a;每个人都有一个友善值#xff0c;当两个A国人的友善值a、b#xff0c;如果a xor b mod 21#xff0c;那么这两个人都是朋友#x… 题目链接bzoj2744 题目大意 两个国家看成是AB两国现在是两个国家的描述 1.A国每个人都有一个友善值当两个A国人的友善值a、b如果a xor b mod 21那么这两个人都是朋友否则不是 2.B国每个人都有一个友善值当两个B国人的友善值a、b如果a xor b mod 20 或者 (a or b)化成二进制有奇数个1那么两个人是朋友否则不是朋友 3.A、B两国之间的人也有可能是朋友数据中将会给出A、B之间“朋友”的情况。 4.在AB两国朋友圈的定义一个朋友圈集合S满足S∈A∪B,对于所有的ij∈Si和j是朋友 求出最大朋友圈的人数 题解 匈牙利求二分图的最大匹配 %%%[迷の想到tarjan的我ORZ... 这个题的意思是要我们求一个图的最大团。嗯。一定有特殊性质才使这道题可做。 首先观察A国人a xor b mod 21就是说当且仅当这两人一奇一偶的时候才为朋友就是说A国的相当于一个二分图。而二分图的最大团只有2。 然后看B国人可以发现奇数间是个完全图偶数间也是(在先不考虑第二个条件的情况下)。那么它的补图就是个二分图考虑埋第二个条件也是。而在某图是个二分图的前提下其最大独立子集就等于它补图的最大团。于是我们构图的时候就直接构造它的补图其实就是把每对奇偶都连上..(额不要忘了去掉满足第二个条件的)。然后跑匈牙利就好了。 所以做法就是枚举A国选多少人(0,1,2)哪些人。根据选出来的A国人选出能与所有被选到的A国人成为朋友的B国人构图(如上所述的那样↑)上匈牙利。因为有最大独立子集总点数-最大匹配算出来后加上A国的人数就好了。 ..我觉得我的代码还是算好懂的吧用了时间戳。嗯。 #includecstdio
#includecstdlib
#includecstring
#includealgorithm
#includeiostream
using namespace std;
#define maxn 250
#define maxm 3100int A[maxn],B[maxm];
int len,lem,bf[maxm];
int ask[maxm],tim;//用时间戳
int ln[maxm],lm[maxm];
bool bk[maxm][maxm],bo[maxn][maxm];
//bk[i][j]存B国中i,j是否突破了奇偶限制而成为了朋友
int mymax(int x,int y){return (xy)?x:y;}
bool ffind(int x)
{int i;for (i1;ilem;i)if (ask[i]!tim !bk[ln[x]][lm[i]])//如果成为了朋友 那么补图中他们两个是不能连边的{ask[i]tim;if (bf[i]-1 || ffind(bf[i])){bf[i]x;return true;}}return false;
}
bool count(int x)
{int ret0;while (x){if (x1) ret;x1;}return ret1;
}
int main()
{//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);int n,m,r,i,j,k,x,y,ia,num,ans;scanf(%d%d%d,n,m,r);for (i1;in;i)scanf(%d,A[i]);for (i1;im;i)scanf(%d,B[i]);memset(bo,false,sizeof(bo));memset(bk,false,sizeof(bk));for (i1;ir;i){scanf(%d%d,x,y);bo[x][y]true;}for (i1;im;i)for (ji1;jm;j)if ((B[i]B[j])1){if (count(B[i]|B[j])) bk[i][j]bk[j][i]true;}memset(ask,0,sizeof(ask));anstim0;lenlemnum0;for (i1;im;i)if (B[i]1) ln[len]i;else lm[lem]i;memset(bf,-1,sizeof(bf));for (i1;ilen;i){tim;if (ffind(i)) num;}ansmymax(ans,lenlem-num);for (i1;in;i){lenlemnum0;for (j1;jm;j)if (bo[i][j]){if (B[j]1) ln[len]j;else lm[lem]j;}memset(bf,-1,sizeof(bf));for (j1;jlen;j){tim;if (ffind(j)) num;}ansmymax(ans,1lenlem-num);}for (i1;in;i)for (ji1;jn;j) if ((A[i]A[j])1){lenlemnum0;for (k1;km;k)if (bo[i][k] bo[j][k]){if (B[k]1) ln[len]k;else lm[lem]k;}memset(bf,-1,sizeof(bf));for (k1;klen;k){tim;if (ffind(k)) num;}ansmymax(ans,2lenlem-num);}printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/Euryale-Rose/p/6527806.html
