[CF1525F]Goblins And Gnomes

题目

传送门 to CF

题目描述
有一个游戏叫《杀死地精》，一共有 $k$ 波攻势，第 $i$ 轮将会有 $i$ 个哥布林。

地精有 $n$ 座城市，有 $m$ 条单向隧道连接着它们。隧道的设计非常巧妙，使得哥布林离开一个城市之后，无论如何也不能再次回到这个地方。当然啦，任意两个城市之间的隧道只有一条。

哥布林非常贪婪。每个哥布林会劫掠它移动路径上的所有城市。在第 $i$ 轮中，每个哥布林出现在不同的城市，然后开始移动。城市不会被劫掠多次，即两个哥布林的路径不相交。在此基础上，它们会找到劫掠城市总数最大的方案。如果有多个呢？它们会随机选择一个。

在每一轮中，一旦 $n$ 个城市都被劫掠了，那你就失败了。否则，我们可以东山再起——所有城市都会恢复。所以在下一轮中，哥布林仍然对所有城市都感兴趣。

这个游戏的得分比较复杂。为了防御哥布林，在每轮之前，你可以进行两种操作：将所有离开 $i$ 城市的路径关闭；将所有进入 $i$ 城市的路径关闭。这个操作永久生效。但是第 $i$ 轮之前，如果你操作了 $t$ 次，那么你这一轮的得分是 $\max (x_i-t\cdot y_i,0)$，其中 $x_i,y_i$ 是固定的参数。

你需要最大化每一轮得分的和。前提是，你的操作是 $100\%$ 必胜的！

数据范围与提示
$2\le n\le 50$ 且 $1\le k\le n-1$ 。边的数量无特殊限制，即 $0\le m\le \frac{n(n-1)}{2}$ 。

思路

其实这个题面真的晦涩难懂。简单一点就是：想办法使得最小链划分 $>i$，保证图是 $\mathrm{D}\mathrm{A}\mathrm{G}$，最大化分数。

那么最小链划分有个经典操作，是 二分图匹配。虽然直接理解比较容易，但是不好想到啊……我粗略写一下我是怎么推出来的。

我先建立了最小费用有源汇上下界可行流的模型。每个点拆成入度和出度两个点，二者之间有一条下界为 $1$、上界也为 $1$ 的边。$S$ 到每个 $in$（代表入度的点）有一条代价为 $1$、容量为 $1$ 的边。同理 $out$ 到 $T$ 有容量为 $1$ 代价为 $0$ 的边。

然后把图建出来。$SS$ 向 $out$ 连边，容量为 $1$ 。$in$ 向 $TT$ 连边，容量为 $1$ 。$S$ 向 $in$ 和 $out$ 向 $T$ 和 $out$ 向 $in$ 的边保留，额外加了一个 $T\to S$ 容量为 $+\infty$ 。

整理一下上面的东西，就是 $SS\to out\stackrel{edge}{⟶}in\to TT$ 和 $out\to T\to S\stackrel{cost=1}{⟶}in$，最终要求是 $SS$ 到 $TT$ 满流，且代价最小。可以看出就是 $in$ 和 $out$ 作匹配，如果有边可以直接匹配，否则用 $S,T$ 中转，代价为 $1$ 。显然目标转化为最大化 $in$ 和 $out$ 用边直接匹配。$\Rightarrow$ 最小链覆盖 $=n-$ 最大匹配。

重新看操作，发现就是删掉二分图中的一个点。而我们有一个很强大的结论是，如果 $⟨i,j⟩$ 在最大匹配中，那么删掉 $i$ 和删掉 $j$ 总有一个可以使得最大匹配减小。

有两个不错的证明方法。其一是我考场上口胡的：反证法。如果删掉 $i$ 不让匹配变少，肯定是 $j$ 可以重新增广。同理，必须要 $i$ 也可以重新增广。把这两条路径和 $⟨i,j⟩$ 拼起来，就得到了一条增广路径，与最大匹配矛盾。（一个神奇的事情是，增广路径可以有环，只要保留经过奇数次的边就行。）

其二是官方题解更优美的证法：众所周知，最小点覆盖 $=$ 最大匹配，构造方法是，每条匹配的边都选择某个端点。所以 $i,j$ 之中的某一个是最小点覆盖中的点。将其删去，最小点覆盖当然减小，所以最大匹配减小。

证明了这个，我们就会发现，每次操作哪个点不重要，反正就是可以让最大匹配减小。那么具体怎么操作就成为了 $\mathtt{d}\mathtt{p}$ 的问题。构造方案也就可以这么做。复杂度 $\mathcal{O}(n^3)$ 。

代码

调了很久，原因竟然是：fakeDfs 在递归时调用了 dfs 函数！警示：函数名不要太相似。这个错误竟然连 $\mathsf{H}\mathsf{a}\mathsf{n}\mathsf{d}\mathsf{I}\mathsf{n}\mathsf{D}\mathsf{e}\mathsf{v}\mathsf{i}\mathsf{l}$ 也没有发现，嘿嘿！

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){ 
   
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int_ x){ 
   
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}
inline int ABS(const int &x){ 
   
	return x < 0 ? -x : x;
}

const int MaxN = 55;
const int_ infty = (1ll<<62)-1;

int match[MaxN<<1];
bool vis[MaxN<<1], zxy[MaxN<<1];
vector<int> g[MaxN<<1];
bool dfs(int x){ 
   
	if(vis[x] || zxy[x]) return false;
	else vis[x] = true;
	for(int y : g[x]) if(!zxy[y])
		if(!match[y] || dfs(match[y])){ 
   
			match[x] = y, match[y] = x;
			return true; // find mate
		}
	return false; // fail
}
bool fakeDfs(int x){ 
   
	if(vis[x] || zxy[x]) return false;
	else vis[x] = true;
	for(int y : g[x]) if(!zxy[y])
		if(!match[y] || fakeDfs(match[y]))
			return true; // don't change anything
	return false; // fail
}

long long dp[MaxN][MaxN];
int pre[MaxN][MaxN], n;
vector<int> ans;
void print(int x,int y){ 
   
	if(!x) return ;
	print(x-1,pre[x][y]);
	int t = pre[x][y]-y;
	for(int i=1; i<=n&&t; ++i)
		if(match[i]){ 
   
			int jb = match[i];
			memset(vis+1,0,sizeof(vis));
			zxy[jb] = true; // deleted
			if(!fakeDfs(i))
				ans.push_back(n-jb);
			else{ 
   
				ans.push_back(i);
				zxy[i] = true;
				zxy[jb] = false; // not deleted
			}
			match[i] = match[jb] = 0;
			-- t; // fucked one
		}
	ans.push_back(0);
}
int main(){ 
   
	n = readint();
	int m = readint(), k = readint();
	for(int i=1,a,b; i<=m; ++i){ 
   
		a = readint(), b = readint();
		g[a].push_back(b+n);
		g[b+n].push_back(a);
	}
	int cnt = 0;
	for(int i=1; i<=n; ++i)
		if(!match[i]){ 
   
			memset(vis+1,0,n<<1);
			if(dfs(i)) ++ cnt;
		}
	rep(i,0,n) rep(j,0,n)
		dp[i][j] = -infty;
	dp[0][cnt] = 0; // zero score
	rep(i,1,k){ 
   
		int x = readint(), y = readint();
		rep(j,0,n) rep(t,0,j)
			if(dp[i][j-t] < dp[i-1][j]+max(0ll,x-1ll*t*y)){ 
   
				dp[i][j-t] = dp[i-1][j]+max(0ll,x-1ll*t*y);
				pre[i][j-t] = j;
			}
		rep(j,n-i,n) dp[i][j] = -infty;
	}
	int id = 0;
	rep(j,0,n-k-1) if(dp[k][j] > dp[k][id]) id = j;
	print(k,id);
	int len = ans.size();
	printf("%d\n",len);
	for(int i=0; i<len; ++i)
		printf("%d ",ans[i]);
	puts("");
	return 0;
}

今天的文章[CF1525F]Goblins And Gnomes分享到此就结束了，感谢您的阅读。