E.Emotion(2019武大校赛现场赛)(吉比特杯第二届湖北省程序设计大赛)(二分图匹配) 解题报告 Apare_xzc

E.Emotion(2019武大校赛现场赛)(吉比特杯第二届湖北省程序设计大赛)(二分图匹配) 解题报告

xzc 2019/4/18

CCNU_你们好强啊我们都是面包手

题意：
  GHK这个人喜欢玩“问道”这款手游，他喜欢收集一款飞行灵兽。飞行灵兽可以升级，升级以后它的速度，伤害，防御和其它属性都会提升。他发现幽灵之魂(ghosts)和帝王之魂(impreial spirits)可以结合，从而使得飞行灵兽的属性提升。
  现在他手中的幽灵之魂和帝王之魂一共有N个，现在GHK的死对头TYT要求GHK给它尽可能多的ghosts和imperia spirits。GHK当然不想让死对头得到好处，他决定挑出尽可能多的K个两种魂，且这K个任意两个不能配对。他想知道K最大可以为多少。
  注：两种魂共N个，序号为0~N-1，x和y代表一对可结合的两种魂的序号(若x是ghost,那么y一定是imperial spirit，不然的话就x是imperial spirit,y是ghost)。
  x和y满足下列关系：

当x>=N/2时 y = ((A*x)^B)%(N/2)  
当x<N/2时  y = ((B*x)^A)%(N/2)+(N/2)
N/2为整数除法，%为取模运算，^为按位异或
A，B是题目给出的参数

输入：
第一行一个T，表示有T组测试数据
接下来T行，每行三个整数N,A,B

输出：
T行，每行一个整数表示答案

数据范围：
1<=T<=10
2<=N<=3000
0<=A,B<=1E6

Example input:

2
6 0 0
6 3 4

Example output:

4
3

分析(上题解)：

• 容易发现 0~N/2-1 喜欢的数字是 N/2~N , N/2~N 喜欢的数字是 0~N/2-1
• 所以，0～N-1构成一张二分图，抽取k个点，互相没有感情，就是求最大独立集
• 最大独立集合 = 总点数 - 最大匹配数
• 求二分图最大匹配可以网络流或者匈牙利算法

  我用的是网络流算法求最大匹配数(网络流大法好)
思路是这样的：

1. 设要匹配的二分图的两个点集合为U和V，设n=floor(N/2)则U中点的编号都在[0,n-1]的范围内，V中点的编号都在[n,N-1]的范围内
2. 我们建立原点S和汇点T,不妨给S编号为N号节点，给T编号为N+1号节点
3. 我们开始构图。原点S对于集合U中的每一个元素连一条容量为1的有向边。集合V的每一个每一个元素连一条道汇点T的容量为1的有向边。然后原来U,V之间的边照样连，容量也为1。
4. 构图之后，由于网络流的性质，从原点到汇点的的最大流就是最大匹配数量

我目前只会Ford-Fulkerson,看了网上很多板子，用数组模拟链表改写了

我的代码：

/* E. Emotion Author: CCNU xzc time: 560ms state: AC 2019/4/17 17:11 */
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
using namespace std;
const int maxn = 310;
const int maxm = 2e3;
int A,B,N,n; //N<=300 
struct Edge{
	int from,to,Next,rev; 
}edge[maxm];
int head[maxn],tot;
int flow[maxm],pre[maxn],IdEdge[maxn],st,ed;
int f2(int);
int f1(int);
void initG();
void addedge(int,int,int); 
int bfs();
void solve(); 
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;scanf("%d",&T);
    while(T--)
    {
    	scanf("%d%d%d",&N,&A,&B);
    	n = N/2;
    	initG();
    	st = N;ed = N+1;
    	For(u,0,n-1)
    	{
    		int v = f1(u);
    		addedge(st,u,1);
    		addedge(u,v,1);
		}
		For(u,n,N-1)
		{
			int v = f2(u);
			addedge(u,ed,1);
			addedge(v,u,1);
		} 
		solve();
	}
    return 0;
}
int f2(int x)
{
	return ((A*x)^B)%n;
}
int f1(int x)
{
	return ((B*x)^A)%n+n;
}
void initG()
{
	tot = 0;
	Mst(head,-1);
	Mst(flow,0);//流量置为0 
}
void addedge(int u,int v,int f)
{
	flow[tot] += f;
	edge[tot].from = u;
	edge[tot].to = v;
	edge[tot].rev = tot+1;
	edge[tot].Next = head[u];
	head[u] = tot++;//下面开始建反向边 
	edge[tot].from = v;
	edge[tot].to = u;
	edge[tot].rev = tot-1;
	edge[tot].Next = head[v];
	head[v] = tot++; 
}
int bfs()
{
	Mst(pre,-1);
	queue<int> Q;
	pre[st] = 0;
	Q.push(st);
	bool flag = false;
	while(!Q.empty()&&!flag)
	{
		int u = Q.front();Q.pop();
		for(int i=head[u];i!=-1;i=edge[i].Next)
		{
			int v = edge[i].to;
			if(flow[i]>0&&pre[v]==-1)
			{
				pre[v] = u;
				IdEdge[v] = i;
				Q.push(v);
				if(v==ed) 
				{
					flag = true;
					break;	
				}	
			} 
		} 
	}
	if(!flag) return 0;
	int v = ed;
	int add = 2e9;
	while(v!=st)
	{
		int id = IdEdge[v];
		add = min(add,flow[id]);
		v = pre[v];
	}
	v = ed;
	while(v!=st)
	{
		int id = IdEdge[v];
		int r = edge[id].rev;
		flow[id] -= add;
		flow[r]  += add;
		v = pre[v];
	}
	return add;
}
void solve()
{
	int ans = 0, add = 0;
	while(1)
	{
		add = bfs(); 
		if(!add) break;
		ans += add;
	} 
	printf("%d\n",N-ans);
}

附:所有测试数据：

input:

12
6 0 0
6 3 4
211 418178 32278
230 282923 473099
255 218252 352410
74 998575 854744
57 427806 733718
33 491362 20360
50 0 0
300 12345 56789
150 0 3
200 1 0

Answer:

4
3
126
129
145
43
38
24
48
177
124
100

附:武大出题人的标程(匈牙利算法)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define maxn 305
int cx[maxn],cy[maxn];
int visited[maxn];
int edges[maxn][maxn];
int N,A,B;

int path(int u){
	int v;
	for(v=N/2;v<N;v++){
		if(edges[u][v] && !visited[v]){
			visited[v] = 1;
			if(cy[v]==-1 || path(cy[v])){
				cx[u] = v;
				cy[v] = u;
				return 1;
			}
		}
	}
	return 0;
}
int maxMatch(){
	int res = 0;
	memset(cx,0xff,sizeof(cx));
	memset(cy,0xff,sizeof(cy));
	int Nx = N/2;
	for(int i=0;i<Nx;i++){
		if(cx[i]==-1){
			memset(visited,0,sizeof(visited));
			res += path(i);
		}
	}
	return res;
}

void build(){
	memset(edges,0,sizeof(edges));
	for(int i=0;i<N;i++){
		int y,x=i;
		if(i>=N/2){
			y = ((A*x)^B)%(N/2);
			edges[y][i] = 1;
		}else{
			y = ((B*x)^A)%(N/2)+N/2;
			edges[i][y] = 1;
		}
	}
}
int main(){
	 freopen("in.txt","r",stdin);
	 freopen("stdout.txt","w",stdout);

	int T;
	cin>>T;
	while(T--){
		cin>>N>>A>>B;
		build();
		int ans = N - maxMatch();
		cout<<ans<<endl;
	}
	return 0;
}