「SOL」Tug of War(洛谷) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

「SOL」Tug of War(洛谷)

发表于 更新于 分类于 Valine：

至理名言「deadline 是第一生产力」

# 题面

有 $2n$ 个人，分成两个队(A,B)拔河。其中第 $i$ 个人若参加 A 队，则只能站在 A 队的 $a_i$ 位置；若参加 B 队，则只能站在 $b_i$ 位置；并且他的力量为 $k_i$。

要求两队都恰有 $n$ 个人，同一个位置不能站多个人，并且两队的力量之差不超过 $K$。

求是否存在满足要求的方案。

数据规模：$1\le n\le3\times10^4$，$k_i\le20$

# 解析

不管「力量差不超过 $K$」的限制，先看看什么时候存在合法的分组。

做过类似的题，把一个人看作一条边 $(a_i,b_i+n)$，可以转化为图论模型。

那么在这个模型中，点表示队伍中的位置，边表示人。一条边只能“占据”其端点的位置，于是可以转化为「给边定向，使得每个点恰有一个入度」的问题。

首先必须满足每个连通块的点数等于边数，这意味着每个连通块恰有一个环（基环树）。

再推导一下。我们从基环树上总度数为 $1$ 的点开始给边定向，发现与它连接的唯一一条边的方向是固定指向它的。于是定向后删去该点和边，继续处理子问题。

于是我们可以发现——基环树上非环上边的方向是固定的。而环上的边则显然存在两种方案（“顺时针”和“逆时针”）。

我们不妨计算「A 队总力量 - B 队总力量」，则定义一个有向边的边权——若指向 $a_i$，边权为 $+k_i$；指向 $b_i$ 则为 $-k_i$。

先随便给环定个向，对每个基环树算出其环的权 $c$ 和非环边的权 $l$，则易得整个基环树的权只可能为 $l\pm c$。

这样我们做一个「0-1背包」，而且注意到 dp 值是 bool，常规操作用 bitset 进行优化，记 $S=20n$，则复杂度 $\mathcal{O}(\frac{Sn}{w})$。

直接这么做不开 O2 是卡不过的，考虑继续优化。

注意到上述背包的所有物品的大小总和不超过 $S$，那么这意味着大小不同的物品总数是 $\mathcal{O}(\sqrt S)$ 的——大小超过 $\sqrt S$ 的物品至多有 $\sqrt S$ 种，小于 $\sqrt S$ 的物品本来就只有 $\sqrt{S}$ 种。

于是将「0-1背包」转化为「多重背包」，最后利用二进制分组重新转化为物品数为 $\mathcal{O}(\sqrt{S}\log n)$ 的「0-1背包」。

再次利用 bitset 将时间复杂度降至 $\mathcal{O}(\frac{S^{1.5}\log n}{w})$。的确是一道分析和优化思路都很清晰的好题。

# 源代码

点击展开/折叠代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/*Lucky_Glass*/
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int rin(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
const int N=3e4+10;
#define con(type) const type &

struct Dsu{
	int fa[N<<1];
	bool tag[N<<1];
	inline int findFa(con(int)u){return fa[u]==u?u:fa[u]=findFa(fa[u]);}
	inline bool merge(int u,int v){
		u=findFa(u),v=findFa(v);
		if(u==v){
			if(tag[u]) return false;
			return tag[u]=true;
		}
		if(tag[u] && tag[v]) return false;
		fa[u]=v,tag[v]|=tag[u];
		return true;
	}
	void init(con(int)n){
		for(int i=1;i<=n;i++)
			fa[i]=i,tag[i]=false;
	}
}ds;
struct Graph{
	int head[N<<1],to[N<<2],nxt[N<<2],len[N<<2],ncnt;
	Graph(){ncnt=1;}
	void addEdge(con(int)u,con(int)v,con(int)l){
		int p=++ncnt,q=++ncnt;
		to[p]=v,nxt[p]=head[u],len[p]=l,head[u]=p;
		to[q]=u,nxt[q]=head[v],len[q]=l,head[v]=q;
	}
	inline int operator [](con(int)u){return head[u];}
}gr;

int n,bonk,rcir,rlis,nval_bin,nval;
int dep[N<<1],val_bin[N],val[N];
bitset<N*40> dp[2];
bool covered[N<<1];

bool searchDFS(con(int)u,con(int)las_edg){
	bool oncir=false,fix_end=false;
	for(int it=gr[u];it;it=gr.nxt[it]){
		int v=gr.to[it];
		if((it>>1)==las_edg) continue;
		if(dep[v]){
			if(dep[v]<dep[u]){
				oncir=true;
				covered[v]=true;
				if(v>n) rcir+=gr.len[it];
				else rcir-=gr.len[it];
			}
			else fix_end=true;
			continue;
		}
		dep[v]=dep[u]+1;
		if(searchDFS(v,it>>1)){
			oncir=true;
			if(v>n) rcir+=gr.len[it];
			else rcir-=gr.len[it];
		}
		else{
			if(covered[v]){
				covered[u]=true;
				if(u>n) rlis+=gr.len[it];
				else rlis-=gr.len[it];
			}
			else
				if(v>n) rlis+=gr.len[it];
				else rlis-=gr.len[it];
		}
	}
	return !fix_end && oncir;
}
int main(){
	// freopen("input.in","r",stdin);
	rin(n),rin(bonk);
	ds.init(n<<1);
	for(int i=1,li,ri,ki;i<=2*n;i++){
		rin(li),ri=rin(ri)+n,rin(ki);
		if(!ds.merge(li,ri)){printf("NO\n");return 0;}
		gr.addEdge(li,ri,ki);
	}
	for(int i=1;i<=2*n;i++)
		if(ds.fa[i]==i && !ds.tag[i]){
			printf("NO\n");
			return 0;
		}
	int ini_val=0;
	for(int i=1;i<=2*n;i++)
		if(!dep[i]){
			dep[i]=1;
			rlis=rcir=0,searchDFS(i,-1);
			// printf("? %d %d\n",rlis+rcir,rlis-rcir);
			if(rcir>0){
				ini_val+=rlis-rcir;
				val_bin[++nval_bin]=rcir<<1;
			}
			else{
				ini_val+=rlis+rcir;
				val_bin[++nval_bin]=(-rcir)<<1;
			}
		}
	sort(val_bin+1,val_bin+1+nval_bin);
	for(int i=1;i<=nval_bin;i++){
		int ii=i,siz;
		while(ii<nval_bin && val_bin[ii+1]==val_bin[i]) ii++;
		siz=ii-i+1;
		for(int j=1;j<=siz;j<<=1){
			val[++nval]=j*val_bin[i];
			siz-=j;
		}
		if(siz) val[++nval]=siz*val_bin[i];
		i=ii;
	}
	dp[0][0]=1;
	int I=1;
	for(int i=1;i<=nval;i++,I^=1)
		dp[I]=dp[!I]|(dp[!I]<<val[i]);
	for(int i=max(-bonk-ini_val,0);i<=min(bonk-ini_val,40*N-1);i++)
		if(dp[I][i]){
			printf("YES\n");
			return 0;
		}
	printf("NO\n");
	return 0;
}

当时迷雾正浓 谎称歌颂
斥退肆虐的兽 幸得荣宠
笑我成疯成魔 呐喊汹涌
情深索性无终 登上灵鹫

——《你是我遥不可及的梦》By 苍穹/papaw泡泡

> Link 你是我遥不可及的梦-Bilibili