最小割必刷题！

首先我们先把棋盘看作二分图黑白染色，比如我们可以把横纵坐标加起来为奇数的看作黑，偶数看作白。

考虑到一个黑色节点只会对它四周的节点产生影响，不难想到我们直接把把源点往所有黑点连边权为这个点在棋盘上的数的边，白点同理，只是往汇点连边，然后相邻的方格之间连无穷大的边，这样这些边就不会被算在割边中。

那我们对于舍弃一个点，就是把这个点往源点或汇点的边割掉，dinic跑最小割即可。（ISAP不会写QAQ)

一道好题。

这是一个树形结构，我们可以先拍成 $dfn$ 序，然后对于每个星球，本质上就是在其子树内区间再 删去一些小子树 所构成的一些区间，因为最多 $n$ 个操作，所以区间最多 $\mathcal{O}(n)$ 个，线段树分治，把这些区间插入，然后我们考虑如何求答案。

$y,z$ 是没用的，最终答案即为 $(x_0 - x)^2 + c$，拆开得 $- 2x_0x + {x_0}^2 + x^2 + c$。

我们考虑斜率优化，在看这个式子 $s = - 2x_0x + {x_0}^2 + x^2 + c$，移项得 $x^2 + c = 2x_0x - {x_0}^2 + s$，即点 $(x,x^2 + c)$ 斜率为 $2x_0$，维护下凸包即可，若二分则复杂度是 $\mathcal{O}(n\log^2{n})$，只需将 $x$ 与斜率 $x_0$ 都从小到大排序，我们可以利用单调栈达成 $\mathcal{O}(n\log{n})$ 的复杂度。

http://218.28.19.228:8081/cogs/index.php书架二题解

书架2的问题可以转化为求集合中所有子集的问题（每个牛堆是一个子集）用牛高度的加和减书架高度，求最小值。

本题有两种方法

1.搜索 2.状态压缩

状态压缩求子集：

用一个二进制数表示是否选取某个集合元素（1为子集中有此位置元素，0为没有），每次+1，枚举所有子集

下面是状态压缩代码

#include<bits/stdc++.h> 
using namespace std;
int er[25]={0};
int ii=0;
void erj(int a)
{
    while(a!=0)
    {
        er[ii]=a%2;
        a/=2;
        ii++;
    }
}
int main()
{
    freopen("shelf2.in","r",stdin);
    freopen("shelf2.out","w",stdout);
    int n,b;
    cin>>n>>b;
    int a=pow(2,n+1);
    int n1[25]={0};
    for(int i=0;i<n;i++)cin>>n1[i];
    int sum=0,ans=9999999;
    for(int i=0;i<a;i++)
    {
        erj(i);
        for(int j=0;j<ii;j++)
        {
            if(er[j])sum+=n1[j];
        }
        if(sum>=b)
        {
            ans=min(ans,sum-b);
        }
        sum=0;
        ii=0;
        memset(er,0,sizeof(er));
    }
    cout<<ans;
    return 0;
}

 更新时间：

  2001.9.11

COGS 1825 [USACO Jan11]道路与航线

由于 $T \leq 25000,R+P \leq 100000$ ，优先考虑SPFA，

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	memset(p, 0, sizeof(p));
	queue<int> q;
	q.push(s);
	vis[s] = true;
	d[s] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		vis[x] = 0;
		for (int i = 0; i < v[x].size(); i++) {
			if (d[v[x][i].first] > d[x] + v[x][i].second) {
				d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
				if (!vis[v[x][i].first]) q.push(v[x][i].first), vis[v[x][i].first] = true;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> R >> P >> S;
	for (int i = 1; i <= R; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= P; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
	SPFA(S);
	for (int i = 1; i <= T; i++) {
		if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
		else cout << d[i] << endl;
	}
	return 0;
}

最终评测T两个点，考虑换方法。

查看资料注意到SPFA有双端队列优化和优先队列优化，优先队列复杂度 $O(logn)$，故不考虑。双端队列优化思路是：将要加入的节点与队头比较，小于等于插到队头，大于则插到队尾，时间复杂度接近 $O(1)$。

重写代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	memset(p, 0, sizeof(p));
	deque<int> q;
	q.push_back(s);
	vis[s] = true;
	d[s] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop_front();
		vis[x] = 0;
		for (int i = 0; i < v[x].size(); i++) {
			if (d[v[x][i].first] > d[x] + v[x][i].second) {
				d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
				//主要改动如下
				if (!vis[v[x][i].first]) {
					if (d[v[x][i].first] <= d[q.front()]) q.push_front(v[x][i].first);
					else q.push_back(v[x][i].first);
					vis[v[x][i].first] = true;
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> R >> P >> S;
	for (int i = 1; i <= R; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= P; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
	SPFA(S);
	for (int i = 1; i <= T; i++) {
		if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
		else cout << d[i] << endl;
	}
	return 0;
}

后记

在知乎上看到文章关于SPFA的各种优化以及对应hack，可以参考（如何看待 SPFA 算法已死这种说法？ - 知乎 (zhihu.com)）。

$题目大意$

${求}\sum_{i=1}^{n}\sum _{j=1}^{m}{lcm(i,j)} {且} 1\le n,m\le 1e7$

${正解:}$

${有}{lcm(i,j)=\frac{i\cdot j}{\gcd(i,j)}}$

${所以原式为:}$

$ans(n,m)=\sum_{i=1}^{n}\sum _{j=1}^{m}{\frac{i\cdot j}{\gcd(i,j)}}$

$~\qquad\qquad =\sum_{i=1}^{n}\sum _{j=1}^{m}{ \sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})}{}{\frac{i\cdot j}{d}}}$

${现在需要将d给提出来,默认}{n\le m,}{我们设}i=i'\cdot d,j=j'\cdot d,{则}i'=\frac{i}{d},j'=\frac{j}{d},将i,j替换进上式得:$

$ans(n,m)=\sum_{d=1}^{\min(n,m)}{\sum_{i'=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j'=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i',j')=1]\cdot d\cdot i'\cdot j'}}}$

$~\qquad\qquad=\sum_{d=1}^{n}{d\cdot\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i,j)=1]\cdot i\cdot j}}}$

${接着将d后面的部分再提出来考虑,化简枚举约数,运用莫比乌斯反演:} [\gcd(i,j)=1]=\sum_{d\mid gcd}{\mu{(d)}}:$

${设} \ {g(n,m)}=\sum_{i=1}^{n}{\sum_{j=1}^{m}{[\gcd(i,j)=1]\cdot i\cdot j}}$

$~\qquad\qquad=\sum_{d=1}^{n}{\sum_{d\mid i}^{n}{\sum_{d\mid j}^{m}{\mu(d)\cdot i\cdot j}}}$

${再设}\ i=i' \cdot d,j=j' \cdot d \ {带入,将}\mu{提出来}$

${即}\ g(n,m)=\sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}\cdot{\sum_{i=1}^{\left\lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{i\cdot j}}}}$

$~\qquad\qquad = \sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}}\cdot\frac{{\left \lfloor \frac{n}{d} \right \rfloor}\cdot ({\left \lfloor \frac{n}{d} \right \rfloor}+1)\cdot {\left \lfloor \frac{m}{d} \right \rfloor}\cdot({\left \lfloor \frac{m}{d} \right \rfloor}+1)}{4}$

${最后将g(n,m)带入ans(n,m)中得:}$

$ans(n,m)=\sum_{d=1}^{n}{d}\cdot{g(\left\lfloor \frac{n}{d}\right\rfloor,\left\lfloor \frac{m}{d}\right\rfloor)}$

${用数论分块求出来}~{g(n,m)}~{再用数论分块求出来}~{ans(n,m),}~{就在{\Theta(n+m)内}}{得到答案了}~{(∠・ω< )⌒★}$

通信线路 题解

题目描述

见 通信线路

整体思路

只是一个最小生成树的模板题，数据量也没有很大

第一种方法：kruskal算法

两种实现：边集数组：时间复杂度$O(M log M + M(N + M))$；饼查集 并查集：时间复杂度$O(M log M + kM)$。

第二种方法：Prim算法

时间复杂度：$O(N^2)$（heap优化$O(M long M)$）

读者可以自行实现

代码实现

最小生成树的两个主要算法都可以在讲义中找到，点击这个

本题解采用并查集 + kruskal

好孩子不可以抄代码哦

#include <bits/stdc++.h> // 万能头
using namespace std;
int n; // n是城市数
const int N = 1510,M = 1e4 + 10; // N是最大城市数，M是最大边数
struct Edge // 将边的参数定义到结构体里
{
	int x,y,w; // x起点，y终点，w是权重
}e[M];
bool cmp(Edge &a,Edge &b) // 排序按照权重从小到大
{
	return a.w < b.w;
}
int f[N]; // 并查集数组
void init()
{ // 并查集初始化
	for(int i = 1; i <= N; ++i) f[i] = i;
}
int get(int x)
{ // 递归地查询x属于哪个集
	if(x == f[x]) return x;
	return f[x] = get(f[x]);
}
void merge(int x,int y)
{ // 将两个集合并
	int fx = get(x),fy = get(y);
	if(fx != fy) f[fy] = fx;
}
void kruskal()
{ // kruskal本体
	init(); // 初始化
	int ans = 0;
	for(int i = 1;i <= M;i++)
	{
		int x = e[i].x,y = e[i].y,w = e[i].w; // 每次从边集中取出一个权重较小的
		if(get(x) != get(y)) // 如果这条边的两个顶点不属于同一个集（就是不相连的意思）
		{
			merge(x,y); // 合并，即采用这条边
			ans += w; // 总和记得加哦O(∩_∩)O
		}
	}
	cout << ans << endl; // 输出就好乐，也可以返回ans在主函数里输出
}
int main()
{
	freopen("mcst.in","r",stdin); // 文件输入输出
	freopen("mcst.out","w",stdout);
	cin >> n; // 输入城市数
	int ind = 0;
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < n;j++)
		{
			int op; // 双重循环读入输入的矩阵（确信
			cin >> op; // 第i+1个顶点到第j+1顶点之间边的权重
			if(op != -1) e[ind].x = i + 1,e[ind].y = j + 1,e[ind].w = op,ind++;
			// 如果两个顶点可以有边相连，就放在边集数组
		}
	}
	sort(e,e+M,cmp); // 用cmp来排序
	kruskal(); // kruskal，启动！
	return 0; // 记得return是美德
}