2017-12-30

网络流24题（持续更新）

在做网络流之前，发生了一件非常有趣的事情。
我问蔡爷爷：“大佬，您做的网络流都好神，又神又劲$%%%$”

哇
怎么办
然后和cxy打了网络流24题

搭配飞行员

题意

飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

Solution

裸的二分图匈牙利算法

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int rtn=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(; isdigit(ch);ch=getchar())rtn=(rtn<<1)+(rtn<<3)+ch-'0';
	return rtn*f;
}
const int maxn = 1e4+10;
vector<int>G[maxn];
int n,m,mat[maxn];
bool vis[maxn];
inline bool dfs(int k){
	for(int i=0;i<G[k].size();i++){
		int kk=G[k][i];
		if(vis[kk])continue;
		vis[kk]=true;
		if(!mat[kk]||dfs(mat[kk])){
			mat[kk]=k;
			return true;
		}
	}
	return false;
}
int main(){
#ifdef YSW 
	freopen("data.in","r",stdin);
#endif
	n=read(),m=read();
	int x,y;
	while(~scanf("%d%d",&x,&y)){
		G[x].push_back(y);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(!mat[i])if(dfs(i))ans++; 	
	}
	printf("%d",ans);
	return 0;
}

最小路径覆盖

题意

给定有向图$G=(V,E)$。设 $P$ 是 $G$ 的一个简单路（顶点不相交）的集合。如果 $v$ 中每个顶点恰好在$P$的一条路上，则称 $p$ 是 $G$ 的一个路径覆盖。$p$ 中路径可以从$v$的任何一个顶点开始，长度也是任意的，特别地，可以为0。$G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图$G$的最小路径覆盖。

Solution

一个重要的结论：

$DAG$上的最小路径覆盖 = 顶点数 − 其对应的二分图的最大匹配数

关于证明可以参考网上资料2333

#include <bits/stdc++.h>
const int maxn = 250;
std::stack<int>s;
std::vector<int>G[maxn];
int mat[maxn],ans,out[maxn];
bool vis[maxn];
inline bool dfs(int k){
	for(int i=0;i<G[k].size();i++){
		int kk=G[k][i];
		if(vis[kk])continue;
		vis[kk]=true;
		if(!mat[kk]||dfs(mat[kk])){
			mat[kk]=k;
			return true;
		} 
	}
	return false;
}
int main(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		G[x].push_back(y);
	}	
	int ans=n;
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(dfs(i))ans--;
	}
	for(int i=1;i<=n;i++)out[mat[i]]++;
	for(int i=1;i<=n;i++)if(!out[i]){
		for(int j=i;j;j=mat[j])s.push(j);
			while(s.size())printf("%d ",s.top()),s.pop();
		printf("\n");
	}
	printf("%d",ans);
	return 0;
}

魔术球问题

题意

假设有 $n$ 根柱子，现要按下述规则在这 $n$ 根柱子中依次放入编号为 1,2,3,4⋯ 的球。

每次只能在某根柱子的最上面放球。

在同一根柱子中，任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 $n$ 根柱子上最多能放多少个球。

Solution

我们需要用 $n$ 条不相交的路径尽可能多的去覆盖。
然后可以筛选出可以满足放置条件的点对，很显然小的在下大的在上
对于每一个球我们可以选择将他放在原来已有的一个柱子上或者新开一个柱子。
对于无法放原来的，就只能新开一个柱子。$num > n$ 达到最大

#include <bits/stdc++.h>
using namespace std;
 
const int maxn=101010; 
vector<int>G[maxn];
bool vis[maxn];
int ans[maxn],t,num,mat[maxn];
inline bool dfs(int k){
	for(int i=0;i<G[k].size();i++){
		int kk=G[k][i];
		if(vis[kk])continue;
		vis[kk]=true;
		if(!mat[kk]||dfs(mat[kk])){
			mat[kk]=k;
			return true;
		}
	}
	return false;
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i;i++){
		for(int j=1;j<i;j++)
			if(sqrt(i+j)==(int)sqrt(i+j))
				G[i].push_back(j);
		memset(vis,0,sizeof(vis));
		if(!dfs(i)){
			t++;
			if(t>n){num=i;break;}
			else ans[t]=i;
		}
	}
	cout<<num<<endl;
	for(int i=1;i<=n;i++){
		printf("%d ",ans[i]);
		int j=ans[i];
		while(mat[j]){
			printf("%d ",mat[j]);
			j=mat[j];
		}
		putchar('\n');
	}
	return 0;
}