发布于

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;
}
发布于

lp5145 漂浮的鸭子

一道tarjan缩点的裸题。
我们仍然可以考虑一个很有趣的做法。那就是，把非环边删去，然后统计环的边权。 

#include<iostream>
#include<cstdio>

struct ee{
	int v;
	int w;
}e[100005];

int n,in[100005];
bool vis[100005];

void init(){
	scanf("%d",&n);
	int v,w;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&v,&w);
		e[i]=(ee){v,w};
		++in[v];
	}
	int ans=0,x,nw;
	for(int i=1;i<=n;++i){
		x=i;
		while(!in[x]&&!vis[x]){
			vis[x]=1;
			--in[e[x].v];
			x=e[x].v;
		}
	}
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			nw=e[i].w;
			x=e[i].v;
			vis[i]=1;
			while(x!=i){
				vis[x]=1;
				nw+=e[x].w;
				x=e[x].v;
			}
			ans=std::max(ans,nw);
		}
	}
	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;
}