lp4382 八省联考2018 劈配

扫一眼题目,看到n个点和m个点匹配的问题,你就会有一种预感——是不是要跑二分图匹配?
是的,就是要跑二分图匹配。
第一问很显然,大力让一个导师能够被多个学生匹配,然后跑一个类似于匈牙利的操作。然后如果匹配满了,我们就考虑将这个导师匹配的其他学生尝试匹配同一个优先级的其他节点。
这个复杂度肯定是很松的。
那么关键在于第二问要怎么处理。
观察发现答案具有单调性。也就是说,如果一个选手在较高的优先度会感到沮丧,那么他在一个较低的优先度也会感到沮丧;
因此我们考虑二分答案来检验。
这样的复杂度大概是三方乘对数级的。时间比较紧张。
我们考虑一种优化策略:发现选手提高到某个优先度了以后,他就相当于顶替了本来在这个优先度的选手的位置。
故而,我们可以对于前缀的选手,储存到每个选手时的匹配状态。每次找到某个优先度,就把他的信息加入到对应的匹配状态中,然后跑上述操作。
这样可以优化到平方乘对数级,可能可以通过此题。
这一题的具体操作——也就是那个一点多匹配的操作并不是特别会,以后需要重新研究。
我好菜啊。

#include<iostream>
#include<cstdio>

int c,n,m;
int mx[205],a[205][205],val[205][205][15],exp[205];
int usd[205],usd1[205],usd2[205][205],vis[205];
int prusd[205][205],prusd1[205][205],prusd2[205][205][205];
inline bool dfs(int X,int V){
	int nw,nxt;
	for(int i=1;i<=val[X][V][0];++i){
		nw=val[X][V][i];
		if(vis[nw]){
			continue;
		}
		vis[nw]=1;
		if(usd[nw]<mx[nw]){
			usd1[X]=nw;
			usd2[nw][++usd[nw]]=X;
			return 1;
		}
		for(int j=1;j<=mx[nw];++j){
			nxt=usd2[nw][j];
			if(dfs(nxt,a[nxt][nw])){
				usd1[X]=nw;
				usd2[nw][j]=X;
				return 1;
			}
		}
	}
	return 0;
}
inline void calc1(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		for(int j=1;j<=m;++j){
			if(!val[i][j][0]){
				continue;
			}
			if(dfs(i,j)){
				break;
			}
		}
		for(int j=1;j<=m;++j){
			prusd[i][j]=usd[j];
		}
		for(int j=1;j<=i;++j){
			prusd1[i][j]=usd1[j];
		}
		for(int j=1;j<=m;++j){
			for(int k=1;k<=usd[j];++k){
				prusd2[i][j][k]=usd2[j][k];
			}
		}
	}
}
inline bool chck(int X,int Y){
	for(int i=1;i<=m;++i){
		usd[i]=prusd[Y-1][i];
	}
	for(int i=1;i<=Y-1;++i){
		usd1[i]=prusd1[Y-1][i];
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=usd[i];++j){
			usd2[i][j]=prusd2[Y-1][i][j];
		}
	}
	for(int i=1;i<=m;++i){
		vis[i]=0;
	}
	for(int i=1;i<=exp[X];++i){
		if(!val[X][i][0]){
			continue;
		}
		if(dfs(X,i)){
			return 1;
		}
	}
	return 0;
}
void init(){
//	注意清空数组!!!
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d",&mx[i]);
	}
	for(int i=1;i<=200;++i){
		usd1[i]=0;
		usd[i]=0;
		for(int j=1;j<=200;++j){
			for(int k=0;k<=10;++k){
				val[i][j][k]=0;
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
			if(a[i][j]){
				val[i][a[i][j]][++val[i][a[i][j]][0]]=j;
			}
		}
	}
	for(int i=1;i<=n;++i){
		a[i][0]=m+1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&exp[i]);
	}
	calc1();
	for(int i=1;i<=n;++i){
		printf("%d ",a[i][usd1[i]]);
	}
	puts("");
	int l,r,mid,ans;
	for(int i=1;i<=n;++i){
		if(a[i][usd1[i]]<=exp[i]){
			printf("0 ");
			continue;
		}
		l=1,r=i-1,ans=0;
		while(l<=r){
			mid=(l+r)>>1;
			if(chck(i,mid)){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			} 
		}
		printf("%d ",i-ans);
	}
	puts("");
}

int main(){
	int T;
	scanf("%d%d",&T,&c);
	while(T--){
		init();
	}
	return 0;
}

lp1963 NOI2009 变换序列

如果知道这道题是一个二分图匹配,就显得非常简单了。
首先我们对原序列和变换序列各自建一个点。
然后,对于每一组约束条件\(D_{i}\),我们向所有到\(i\)的距离为\(D_{i}\)的点连一条边。
然后先跑一遍二分图最大匹配。如果全部都能匹配上就说明有解。

但是题目要求字典序输出这组解,怎么办呢?
这么做的意思就是,对于一个尽可能小的数\(i\),它匹配的数\(T_{i}\)也要尽可能小。
故而,搜索的时候从大往小即可。

#include<iostream>
#include<cstdio>
int n,D[10005];
int vis[10005],dep=0;
int usd[10005];

inline bool dfs(int X){
	int up=(X+D[X]-1)%n+1,dw=(X-D[X]+n-1)%n+1;
	if(up<dw){
		std::swap(up,dw);
	}
//	printf("%d %d\n",up,dw);
	if(!usd[dw]&&vis[dw]!=dep){
		vis[dw]=dep;
		usd[dw]=X;
		return 1;
	}
	if(vis[dw]!=dep){
		vis[dw]=dep;
		if(dfs(usd[dw])){
			usd[dw]=X;
			return 1;
		}
	}
	if(!usd[up]&&vis[up]!=dep){
		vis[up]=dep;
		usd[up]=X;
		return 1;
	}
	if(vis[up]!=dep){
		vis[up]=dep;
		if(dfs(usd[up])){
			usd[up]=X;
			return 1;
		}
	}
	
	return 0;
}
int Ans[10005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&D[i]);
	}
	int ans=0;
	for(int i=n;i>=1;--i){
		++dep;
		if(dfs(i)){
			++ans;
		}else{
			break;
		}
	}
	if(ans<n){
		puts("No Answer");
	}else{
		for(int i=1;i<=n;++i){
			Ans[usd[i]]=i;
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]-1);
		}
	}
}

int main(){
	init();
	return 0;
}

lp2764 网络流24题-最小路径覆盖问题


(其实建图方法已经写在题目里了。)
(这一题是一道匈牙利的裸题,考场上二分图最大匹配仍然建议使用匈牙利(因为在实现复杂度上有巨大优势),我纯粹练一下当前弧优化Dinic。)
首先有一个定理。将一张有向图上的每一个点都拆点成入点和出点,连边后形成一张二分图,那么原图的最小路径覆盖,就是顶点数减去这张二分图的最大匹配。
考虑感性地证明这个定理。
每一次匹配,事实上就意味着,一条路径可以额外走过一个点。这样就减少了一个路径覆盖。
所以,当匹配次数最大的时候,路径覆盖数就最小了。
答案用并查集处理一下输出。


#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[2005],et=-1;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}
int dep[2005],nw[2005],f[2005];
int n,m,s,t;

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i; 
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

inline int fnd(int X){
	for(int i=h[X+n];i>=0;i=e[i].nxt){
		if(1<=e[i].v&&e[i].v<=n){
			if(e[i].w){
				return e[i].v;
			}
		}
	}
	return X;
}
inline int fa(int X){
	return f[X]^X?f[X]=fa(f[X]):X;
}
inline void prnt(int X){
	for(int i=h[X];i>=0;i=e[i].nxt){
		if((n+1)<=e[i].v&&e[i].v<=(n<<1)&&!e[i].w){
			printf("%d ",e[i].v-n
			);
			prnt(e[i].v-n);
			return;
		}
	}
}
bool vis[2005];
void init(){
	scanf("%d%d",&n,&m);
	s=(n<<1)+1,t=(n<<1)+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		add(s,i,1);
		add(n+i,t,1);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,n+v,1);
	}
	int ans=n;
	while(bfs()){
		ans-=dfs(s,INF);
	}
	for(int i=1;i<=n;++i){
		f[i]=i;
	}
	for(int i=1;i<=n;++i){
		f[i]=fnd(i);
	}
	for(int i=1;i<=n;++i){
		fa(i);
	}
	for(int i=1;i<=n;++i){
		if(f[i]==i){
			printf("%d ",i);
			prnt(i);
			puts("");
		}
	}
	printf("%d\n",ans); 
}

int main(){
	init();
	return 0;
}

lp5030 长脖子鹿放置

观察这一题的攻击方式,我们可以发现一个特点——所有奇数行的长颈鹿都攻击不到偶数行的长颈鹿,反之亦然。
所以,我们对奇偶的长颈鹿分开考虑,这显然是一张二分图。
于是类同于骑士共存问题,我们建一个二分图,跑匈牙利。
对于\(200\)的数据范围,匈牙利的小常数是可以卡过去的。
但是T了两个点,获得了80分的好成绩。
然后我们考虑一个对于vis数组的常数优化。
对于vis数组,我们定义一个变量dep,表示当前是第dep次匹配。这样就不必每次都清空vis数组了。
第二个就是,由于连的边是确定的,故而我们可以在线计算目的边,这样可以减少很多寻址时间。
另外就是对图的遍历顺序的优化。用了出题人的松松松顺序之后最终通过此题。

#include<iostream>
#include<cstdio>

const int dx[8]={3,3,-3,-3,1,1,-1,-1};
const int dy[8]={-1,1,-1,1,3,-3,3,-3};

bool mp[205][205];
int vis[40405],dep=0;
int n,m,q,usd[40405];
//注意数组大小。 

inline int calc(int X,int Y){
	return (X<=0||Y<=0||X>n||Y>m||mp[X][Y])?0:X*m+Y;
} 

inline bool dfs(int X){
	int v;
	for(int i=0;i<8;++i){
		v=calc((X-1)/m+dx[i],(X-1)%m+1+dy[i]);
//		注意还原信息。 
		if(v&&vis[v]!=dep){
			vis[v]=dep;
			if(!usd[v]||dfs(usd[v])){
				usd[v]=X;
				return 1;
			}
		}
	}
	return 0;
}

void init(){
//	mp[n][m]->mp[x][y] 
	scanf("%d%d%d",&n,&m,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	int ans=n*m-q;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=m;++j){
			if(mp[i][j]){
				continue;
			}
			++dep;
			ans-=dfs(calc(i,j));
		}
	}
//	for(int i=0;i<=n+1;++i){
//		for(int j=0;j<=m+1;++j){
//			printf("%2d ",calc(i,j));
//		}
//		puts("");
//	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp3355 网络流24题-骑士共存问题

首先我们观察这道题。
暴力地状压DP或者之类的操作显然会MLE/TLE。
我们发现,横坐标和纵坐标相加的和的奇偶性相同的格子永远不可能互相攻击到。
故而我们考虑建一张二分图。将横纵坐标的和的奇偶性不同的格子分别放在左右边,然后在能相互攻击到的点之间连边。依据题意,不能相互攻击到,所以答案即是这张图的最大独立集。

二分图最大独立集应当如何求得?我们有一个定理:一张二分图的最大独立集的大小等同于顶点数它的最大匹配的数量。
我们考虑感性地证明这个定理。
很容易可以发现,两个点不能被同时选取,当且仅当它们之间有连边。
又因为,有连边的两个点必然是属于二分图的两端的。
故而,如果有两个点不能被同时选取,它们必然可以构成一个匹配。
对于二分图上的最大匹配,所有没有被匹配的点都可以被选取。这非常的显然,因为没有被匹配到的点之间必然没有连边。如果有连边,那么就可以增加匹配,与最大匹配矛盾。
而,对于每一个匹配,都可以选取一组匹配中的一个点。这是因为,对于一些连通的匹配,它们有且仅有一个部分(左边或者右边)会和未匹配点连接。
这也是很显然的,因为如果不是这样的话,就存在一条新的增广路径,就可以得到更多的匹配了。
注意:坐标如何哈希成一个数字。

#include<iostream>
#include<cstdio>

const int dx[8]={-2,-1,1,2,-2,-1,1,2};
const int dy[8]={1,2,2,1,-1,-2,-2,-1}; 

struct ee{
	int v;
	int nxt;
}e[160005];
int h[40005],et=0;

inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et; 
}

bool vis[40005],mp[205][205];
int n=0,m=0,usd[40005];

inline int calc(int X,int Y){
	return (X-1)*n+Y;
//	注意坐标哈希成数字的方式。 
}

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			vis[e[i].v]=1;
			if(!usd[e[i].v]||dfs(usd[e[i].v])){
				usd[e[i].v]=X;
				return 1;
			}
		}
	}
	return 0;
}
int st[40005],tp=0;
char out[205][205];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			mp[i][j]=0;
			usd[calc(i,j)]=0;
			out[i][j]='O';
		}
	}
	int x,y;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
//			printf("[%d %d] ",i,j);
			if(mp[i][j]||((i+j)&1)){
//				注意不是每次跳2而是判奇偶性。 
				continue;
			}
			st[++tp]=calc(i,j);
			out[i][j]='@'; 
			//注意有障碍的不仅是结束点,还有出发点。 
			for(int k=0;k<8;++k){
				x=i+dx[k],y=j+dy[k];
				if(x<=0||y<=0||x>n||y>n||mp[x][y]){
					continue;
				}
				out[x][y]='X';
				add(calc(i,j),calc(x,y));
			}
		}
	}
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=n;++j){
//			putchar(out[i][j]);
//		}
//		puts("");
//	}
	int ans=n*n-m;
//	减去被挖掉的点 
	for(int i=1;i<=tp;++i){
		for(int j=1;j<=n*n;++j){
			vis[j]=0;
		}
		ans-=dfs(st[i]);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
} 

lp2756 网络流24题-飞行员配对方案问题

这是一个裸的配对问题。
我们可以建成一个二分图然后跑匈牙利。

#include<iostream>
#include<cstdio>
bool mp[105][105],vis[105];
int n,m,usd[105];

inline int dfs(int X){
    for(int i=1;i<=m;++i){
        if(!mp[X][i]){
            continue;
        }
        if(!vis[i]){
            vis[i]=1;
            if(!usd[i]||dfs(usd[i])){
                usd[i]=X;
                return 1;
            }
        }
    }
    return 0;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            mp[i][j]=mp[j][i]=0;
        }
    }
    int x=1,y=1;
    //你绝对想不到的错误——x,y没有初始化,导致判断它们的初始值的时候出现错误。 
    while(x>=0&&y>=0){
        scanf("%d%d",&x,&y);
        y-=n;
        mp[x][y]=1;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            vis[j]=0;
        }
//        for(int j=1;j<=m;++j){
//        	printf("%d ",usd[j]);
//		}
//		puts("");
        ans+=(int)dfs(i);
    }
    printf("%d\n",ans);
    for(int i=1;i<=m;++i){
        if(usd[i]){
            printf("%d %d\n",usd[i],i+n);
            //注意这里要将编号还原。并且别输出反了。 
        }
    } 
}

int main(){
    init();
    return 0;
}

lp3386 二分图最大匹配

一道匈牙利算法的模板题。
对于一张二分图\(G\)(也就是没有奇环的图),我们定义它的「匹配」为一个图\(G'(V’,E’)\),使得:
$$\forall V” \in V’,V”_{u}\in E’,V”_{v}\in E’,|E’|=2|V’|$$
我们称一个匹配是最大匹配,当且仅当它是一个边数最多的匹配。

匈牙利算法是用于求解最大匹配的一类问题。
匈牙利算法使用了一种被称为「增广」的操作。
我们首先定义一条增广路径指的是一张二分图上的路径,使得这条路径的起点和终点都是尚未匹配的点,并且它的路径上经过的所有点都是已经匹配过的点。
那么很容易可以发现,一条增广路径上的边必然是「一条已匹配一条未匹配」的。
于是,我们对增广路径上的所有边的匹配状态取反,就可以增加匹配数量的大小。
增广操作是指,对于一个点,尝试访问它的每一个相邻点,然后从这个相邻点找下去,直到能找到一条增广路径为止。然后将这条增广路径上所有边匹配状态取反。
故而,每一次新加入一个点,我们尝试一次增广。这样就能够找到最大匹配了。

#include<iostream>
#include<cstdio>

int mp[1005][1005];
bool vis[1005];
int n,m,q,usd[1005];
inline bool dfs(int X){
	for(int i=1;i<=m;++i){
		if(!mp[X][i]){
			continue;
		}
		if(!vis[i]){
			vis[i]=1;
			if(!usd[i]||dfs(usd[i])){
				usd[i]=X;
				return 1;
			}
		}
	}
	
	return 0;
}
void init(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			mp[i][j]=mp[j][i]=0;
			usd[i]=usd[j]=0;
		}
	}
	int u,v;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&u,&v);
		if(u>n||v>m){
			continue;
		}
		++mp[u][v];
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		ans+=dfs(i);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}