第一篇： 效果

（违规自删）

两个题分别是P3115和P8074。

源码：

P3115 [USACO15JAN]Cow Routing S题解

题目传送门

1. 题目大意

给你 $n$ 条路线，可以从这条路线上任意一点出发，任意一点结束。无论走过几个城市，花费都是 $w_i$，问从点 $A$ 到点 $B$ 花费最少以及花费最少前提上最少走几个城市，若不能到达，则输出 $-1$。

2. 分析

其实就是一道 dijkstra 的变形，但是是双关键字的。建边时从一条路径从前至后两两建边。我们发现，最少走过城市的数量只与最少花费上有关系，我们只需要以最少花费为关键字来跑一遍 dijkstra 再更新最少走过城市的数量即可（不会 dijkstra 看这里）。

3. 注意事项

先来看一下我曲折的 AC 之路:

其实我大致思路没有问题，只不过没看数据范围，不是数组开大（MLE）了就是小了（RE)。我在这里提醒大家，做题之前，先看数据范围，确定好了数组大小，再写代码。

有 $N$ 条航线，且 $1 \leq N \leq 1000$，每条航线最多包含 $100$ 个城市，每条路线中的城市从前至后两两建边，最多建 $N \times \sum_{i=1}^{k - 1} \ i$ 条路线，代入 $n$、$k$，最多建 $4950000$ 条边。还有一种情况记得特判，费用相等，路径长度要取最小值。最后记得开 long long。

4. Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005, MAXM = 4950005; //最多点数，最多边数
const long long INF = 4557430888798830399; //初始化一个极大值，这里要用long long

int st, fi, n, idx; //起点，终点，点的数量，边的数量 
long long dis[MAXN][2], head[MAXN]; //dis[i][0]为起点到点i最少费用，dis[i][1]为最少费用下的最短路径 
struct Edge{int nxt, to, w, c;}edge[MAXM]; //下一条边，到达的点，费用，路径长度 
struct Node{long long x, w;}; //编号，最少花费 
bool operator < (const Node &a, const Node &b) {return a.w > b.w;} //从小到大排序 
bool vis[MAXN];
priority_queue <Node> q;

void add (int from, int to, int w, int c) //建边 
{
    edge[++idx].nxt = head[from];edge[idx].to = to;edge[idx].w = w;edge[idx].c = c;
    head[from] = idx;
}

void init ()
{
    memset (head, -1, sizeof (head));
    memset (dis, 0x3f, sizeof (dis));
    scanf ("%d%d%d", &st, &fi, &n);
    for (int i = 1; i <= n; i++)
    {
        int k, w;
        long long v[105];
        scanf ("%d%d", &w, &k);
        for (int j = 1; j <= k; j++)    scanf ("%lld", &v[j]);
        //从前至后建边 
        for (int x = 1; x <= k; x++)
        for (int y = x + 1; y <= k; y++)    add (v[x], v[y], w, y - x); //建一条连接v[x]、v[y]费用为w路径长为y - x的边 
    }
}

//堆优化dijkstra
void dijkstar (int s)
{
    dis[s][0] = dis[s][1] = 0;
    q.push (Node {s, 0});
    while (!q.empty ())
    {
        Node cur = q.top ();
        q.pop ();
        if (vis[cur.x]) continue;
        vis[cur.x] = 1;
        for (int i = head[cur.x]; i != -1; i = edge[i].nxt)
        {
            int to = edge[i].to;
            if (dis[to][0] > dis[cur.x][0] + edge[i].w) //若有更小的花费，则更新 
            {
                dis[to][0] = dis[cur.x][0] + edge[i].w;
                dis[to][1] = dis[cur.x][1] + edge[i].c;
                if (vis[to])    continue;
                q.push (Node {to, dis[to][0]}); //入队是入编号和花费 
            }
            if (dis[to][0] == dis[cur.x][0] + edge[i].w) //记得特判费用等于的情况 
            {
                dis[to][1] = min (dis[to][1], dis[cur.x][1] + edge[i].c);//费用等于取路径长度小的 
                if (vis[to])    continue;
                q.push (Node {to, dis[to][0]});
            }
        }
    }
}

void output ()
{
    if (dis[fi][0] == INF)  printf ("-1 -1"); //不能到达 
    else                    printf ("%lld %lld", dis[fi][0], dis[fi][1]);
}

int main ()
{
    init ();        //输入 
    dijkstar (st);  //最短路 
    output ();      //输出 
    return 0;
}

5. 总结

1. 拿到一个题，先仔细读题目，特别是输入输出（有没有换行之类）和数据范围。
2. 分析出题目的特殊情况。

第二篇： 效果

源码：

P8074 [COCI2009-2010#7] SVEMIR题解

题目传送门

1. 题目大意

在一个三维坐标系中，给你 $n$ 个点，建造一个连接 $i$、$j$ 的边的代价是 $\min\{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|\}$，在使得整个图连通时代价最小。

2. 分析

如果打一遍 Prim，时间复杂度为 $O(n^2)$,$1 \le N \le 10^5$，无法 AC。

我们考虑 Kruskal：如果每个点两两建一条边，空间会炸，要优化空间。

我们看一下样例#2:

3
-1 -1 -1 //一号
5 5 5	 //二号
10 10 10 //三号

如果两两建边，会计算大量的无效数据，就像一号和三号点，我们只需要连接一号和二号，那为什么要连一号和三号呢？不难得出，当 $x_a \le x_b \le x_c$ 时，只需连接 $a$、$b$ 和 $b$、$c$，不需要关心 $a$、$c$。$y$、$z$ 也是这样，这样只需建 $3n$ 条边。也就是说，我们按 $x$、$y$、$z$ 从小到大排序再建一条连接相邻两个点的边，最后在跑一边 Kruskal。

3. Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5, MAXM = 1e7;

int n, m, ans, k;
int f[MAXN];
struct Edge {int u, v, w;}edge[MAXM];
bool operator < (const Edge &a, const Edge &b) {return a.w < b.w;}
struct Planet
{
	int x, y, z, id;
	void input (int i) {scanf ("%d%d%d", &x, &y, &z);id = i;}
}planet[MAXN];
bool cmpx (Planet a, Planet b) {return a.x < b.x;}
bool cmpy (Planet a, Planet b) {return a.y < b.y;}
bool cmpz (Planet a, Planet b) {return a.z < b.z;}

void init ()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++)	planet[i].input (i);
	for (int i = 1; i <= n; i++)	f[i] = i;
}

// 并查集 
int find (int x)
{
	if (x != f[x])	f[x] = find (f[x]);
	return f[x];
}

void add (Planet a, Planet b)
{
	edge[++m].u = a.id;edge[m].v = b.id;
	edge[m].w = min (abs (a.x - b.x), min (abs (a.y - b.y), abs (a.z - b.z))); // 计算代价 
}

// 最小生成树 
void Kruska ()
{
	sort (edge + 1, edge + m + 1);
	for (int i = 1; i <= m; i++)
	{
		int r1 = find (edge[i].u), r2 = find (edge[i].v);
		if (r1 == r2)	continue;
		f[r2] = r1;
		k++;ans += edge[i].w;
		if (k == n - 1)	return;// 建好了树就退出 
	}
}

int main()
{
	init ();
	// 排序 + 建一条连接相邻两个点的边
	sort (planet + 1, planet + n + 1, cmpx);
	for (int i = 2; i <= n; i++)	add (planet[i - 1], planet[i]);
	sort (planet + 1, planet + n + 1, cmpy);
	for (int i = 2; i <= n; i++)	add (planet[i - 1], planet[i]);
	sort (planet + 1, planet + n + 1, cmpz);
	for (int i = 2; i <= n; i++)	add (planet[i - 1], planet[i]);
	Kruska ();
	printf ("%d", ans);
    return 0;
}