Timus – Pancake's Personal Website

Timus #1162. Currency Exchange

题目：一共N个货币种类，当前为S种类的货币，当前拥有的该货币价值为V，下面M行包含可以交换货币的汇率/手续费信息：A,B,RAB,CAB,RBA,CBA分别代表种类A，种类B，A到B的汇率，A到B的手续费，B到A的汇率，B到A的手续费。求能否通过某种交换方式能让货币越来越多即大于V。

解析：Bellman-Ford。修改#1450代码即可

#include<iostream>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, s;
float v;

struct Currency
{
	Currency() {
		money = INF;
		done = false;
	}
	//neighbor_index rate commission
	vector<pair<int, pair<float, float>>> neighbor;
	float money;
	bool done;
}currency[100];


void SPFA() {
	queue<int> q;
	currency[s - 1].money = -v;
	q.push(s - 1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		currency[x].done = false;
		for (auto ptr = currency[x].neighbor.begin(); ptr != currency[x].neighbor.end(); ptr++) {
			if (currency[ptr->first].money > -(-currency[x].money - ptr->second.second) * ptr->second.first) {
				currency[ptr->first].money = -(-currency[x].money - ptr->second.second) * ptr->second.first;
				if (!currency[ptr->first].done) {
					currency[ptr->first].done = true;
					q.push(ptr->first);
				}
			}
		}
	}
	if (currency[s - 1].money < v)return;
}

int main() {
	//货币种类 下面共几行 当前货币种类 当前拥有的该货币价值
	cin >> n >> m >> s >> v;
	for (int i = 0; i < m; i++) {
		int a, b;
		float rab, cab, rba, cba;
		cin >> a >> b >> rab >> cab >> rba >> cba;
		currency[a - 1].neighbor.push_back(make_pair(b - 1, make_pair(rab, cab)));
		currency[b - 1].neighbor.push_back(make_pair(a - 1, make_pair(rba, cba)));
	}
	SPFA();
	if (-currency[s - 1].money <= v) cout << "NO" << endl;
	else cout << "YES" << endl;
}

#include<iostream>

#include<vector>

#include<queue>

#define INF 0x3f3f3f3f

using namespace std;

int n, m, s;

float v;

struct Currency

{

Currency() {

money = INF;

done = false;

}

//neighbor_index rate commission

vector<pair<int, pair<float, float>>> neighbor;

float money;

bool done;

}currency[100];

void SPFA() {

queue<int> q;

currency[s - 1].money = -v;

q.push(s - 1);

while (!q.empty()) {

int x = q.front();

q.pop();

currency[x].done = false;

for (auto ptr = currency[x].neighbor.begin(); ptr != currency[x].neighbor.end(); ptr++) {

if (currency[ptr->first].money > -(-currency[x].money - ptr->second.second) * ptr->second.first) {

currency[ptr->first].money = -(-currency[x].money - ptr->second.second) * ptr->second.first;

if (!currency[ptr->first].done) {

currency[ptr->first].done = true;

q.push(ptr->first);

}

if (currency[s - 1].money < v)return;

}

int main() {

//货币种类下面共几行当前货币种类当前拥有的该货币价值

cin >> n >> m >> s >> v;

for (int i = 0; i < m; i++) {

int a, b;

float rab, cab, rba, cba;

cin >> a >> b >> rab >> cab >> rba >> cba;

currency[a - 1].neighbor.push_back(make_pair(b - 1, make_pair(rab, cab)));

currency[b - 1].neighbor.push_back(make_pair(a - 1, make_pair(rba, cba)));

}

SPFA();

if (-currency[s - 1].money <= v) cout << "NO" << endl;

else cout << "YES" << endl;

}

Timus #1160. Network

题目：有N个路由器，给出M个无向连接方式及其长度，需要将所有点可以连接起来，找到最大的连接长度中最小的。但是输出的时候输出总长度没啥关系，你可以输出很多长度小于最小的最大连接长度的点的关系。

解析：最小生成树算法。

我的代码很垃圾，模仿Prim算法，但是把所有相邻信息升序保存在neighbor中，代码写起来更简单，但是复杂度会变大很多很多。（但是能过就行）

#include<iostream>
#include<set>
#include<vector>
using namespace std;

set<pair<int, pair<int, int>>>neighbors;
set<int>node;
set<pair<int, pair<int, int>>>result;

bool in(int i) {
	set<int>::iterator ptr = node.find(i);
	if (ptr != node.end()) return 1;
	else return 0;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		neighbors.insert(make_pair(c, make_pair(a - 1, b - 1)));
	}
	pair<int, int>connection;
	int cost;
	bool a, b;
	node.insert(neighbors.begin()->second.first);
	while (node.size() != n) {
		auto ptr = neighbors.begin();
		while (1) {
			cost = ptr->first;
			connection = ptr->second;
			a = in(connection.first);
			b = in(connection.second);
			if (!a && !b) { 
				ptr++;
				continue;
			}
			if (a && !b) {
				node.insert(connection.second);
				result.insert(make_pair(cost, make_pair(connection.first, connection.second)));
			}
			if (!a && b) {
				node.insert(connection.first);
				result.insert(make_pair(cost, make_pair(connection.first, connection.second)));
			}
			ptr = neighbors.erase(ptr);
			break;
		}
	}
	cout << (--result.end())->first << endl;
	cout << result.size() << endl;
	for (auto i : result) cout << i.second.first + 1 << " " << i.second.second + 1 << endl;
	return 0;
}

#include<iostream>

#include<set>

#include<vector>

using namespace std;

set<pair<int, pair<int, int>>>neighbors;

set<int>node;

set<pair<int, pair<int, int>>>result;

bool in(int i) {

set<int>::iterator ptr = node.find(i);

if (ptr != node.end()) return 1;

else return 0;

}

int main() {

int n, m;

cin >> n >> m;

for (int i = 0; i < m; i++) {

int a, b, c;

cin >> a >> b >> c;

neighbors.insert(make_pair(c, make_pair(a - 1, b - 1)));

}

pair<int, int>connection;

int cost;

bool a, b;

node.insert(neighbors.begin()->second.first);

while (node.size() != n) {

auto ptr = neighbors.begin();

while (1) {

cost = ptr->first;

connection = ptr->second;

a = in(connection.first);

b = in(connection.second);

if (!a && !b) {

ptr++;

continue;

}

if (a && !b) {

node.insert(connection.second);

result.insert(make_pair(cost, make_pair(connection.first, connection.second)));

}

if (!a && b) {

node.insert(connection.first);

result.insert(make_pair(cost, make_pair(connection.first, connection.second)));

}

ptr = neighbors.erase(ptr);

break;

}

cout << (--result.end())->first << endl;

cout << result.size() << endl;

for (auto i : result) cout << i.second.first + 1 << " " << i.second.second + 1 << endl;

return 0;

}

Timus #1450. Russian Pipelines

题目：有n个点，接下来输入m行，表示从a点到b点有向边距离为c，求从S（start）起点到F（Final）终点最大路径。

解析：求最大路径问题
1. Bellman-Ford算法
2. 拓扑，利用入度（In-degree）。从入度等于0（只可能有出度）的点开始拓扑，相邻的点入度-1代表还剩in-degree个点还没拓扑到他，如果该点所有可到他的点均已经寻找完，则把该点加入queue，即可以从该点进行下一步拓扑。

错误提示：
1. WA3 Dijskra算法写错
2. TLE16 Dijskra算法因为只要小于就要加入queue，比入度算法复杂度高，不要用Dijskra改版算法，换算法
3. WA9和WA10。小部分神奇原因：输出强制类型转换成int。大部分原因：不要第一个就从开始点开始拓扑（我也不知道为什么，就是错的）。

Bellman-Ford算法

#include<iostream>
#include<unordered_map>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, beginPoint, endPoint;

struct Point
{
	Point() {
		distence = INF;
		done = false;
	}
	vector<pair<int, int>> neighbor;
	long long distence;
	bool done;
}point[500];


void SPFA() {
	queue<int> q;
	point[beginPoint - 1].distence = 0;
	q.push(beginPoint - 1);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		point[x].done = false;
		for (auto ptr : point[x].neighbor) {
			if (point[ptr.first].distence > point[x].distence - ptr.second) {
				point[ptr.first].distence = point[x].distence - ptr.second;
				if (!point[ptr.first].done) {
					point[ptr.first].done = true;
					q.push(ptr.first);
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		point[a - 1].neighbor.push_back(make_pair(b - 1, c));
	}
	cin >> beginPoint >> endPoint;
	SPFA();
	if (point[endPoint - 1].distence == INF) cout << "No solution" << endl;
	else cout << -point[endPoint - 1].distence << endl;
}

#include<iostream>

#include<unordered_map>

#include<vector>

#include<queue>

#define INF 0x3f3f3f3f

using namespace std;

int n, m, beginPoint, endPoint;

struct Point

{

Point() {

distence = INF;

done = false;

}

vector<pair<int, int>> neighbor;

long long distence;

bool done;

}point[500];

void SPFA() {

queue<int> q;

point[beginPoint - 1].distence = 0;

q.push(beginPoint - 1);

while (!q.empty()) {

int x = q.front();

q.pop();

point[x].done = false;

for (auto ptr : point[x].neighbor) {

if (point[ptr.first].distence > point[x].distence - ptr.second) {

point[ptr.first].distence = point[x].distence - ptr.second;

if (!point[ptr.first].done) {

point[ptr.first].done = true;

q.push(ptr.first);

}

int main() {

cin >> n >> m;

for (int i = 0; i < m; i++) {

int a, b, c;

cin >> a >> b >> c;

point[a - 1].neighbor.push_back(make_pair(b - 1, c));

}

cin >> beginPoint >> endPoint;

SPFA();

if (point[endPoint - 1].distence == INF) cout << "No solution" << endl;

else cout << -point[endPoint - 1].distence << endl;

}

In-degree

#include<iostream>
#include<unordered_map>
#include<vector>
#define INF 0x3f3f3f3f
using namespace std;

int n, m, beginPoint, endPoint;

struct Point
{
	Point() {
		distence = -INF;
	}
	unordered_map<Point*, int> neighbor;
	long long distence;
	int degree;
}point[500];

void extend() {
	vector<Point*>queue;
	point[beginPoint - 1].distence = 0;
	Point* now;
	unordered_map<Point*, int>::iterator ptr;
	for (int i = 0; i < n; i++) 
		if (point[i].degree == 0) 
			queue.push_back(&point[i]);
	while (!queue.empty()) {
		now = *queue.begin();
		queue.erase(queue.begin());
		for (ptr = now->neighbor.begin(); ptr != now->neighbor.end(); ptr++) {
			ptr->first->distence = max(ptr->first->distence, now->distence + ptr->second);
			ptr->first->degree--;
			if (ptr->first->degree == 0) queue.push_back(ptr->first);
		}
		if (point[endPoint - 1].degree == 0) return;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		point[a - 1].neighbor.insert({ &point[b - 1], c });
		point[b - 1].degree++;
	}
	cin >> beginPoint >> endPoint;
	extend();
	if (point[endPoint - 1].distence < 0) cout << "No solution" << endl;
	else cout << point[endPoint - 1].distence << endl;
}

#include<iostream>

#include<unordered_map>

#include<vector>

#define INF 0x3f3f3f3f

using namespace std;

int n, m, beginPoint, endPoint;

struct Point

{

Point() {

distence = -INF;

}

unordered_map<Point*, int> neighbor;

long long distence;

int degree;

}point[500];

void extend() {

vector<Point*>queue;

point[beginPoint - 1].distence = 0;

Point* now;

unordered_map<Point*, int>::iterator ptr;

for (int i = 0; i < n; i++)

if (point[i].degree == 0)

queue.push_back(&point[i]);

while (!queue.empty()) {

now = *queue.begin();

queue.erase(queue.begin());

for (ptr = now->neighbor.begin(); ptr != now->neighbor.end(); ptr++) {

ptr->first->distence = max(ptr->first->distence, now->distence + ptr->second);

ptr->first->degree--;

if (ptr->first->degree == 0) queue.push_back(ptr->first);

}

if (point[endPoint - 1].degree == 0) return;

}

int main() {

cin >> n >> m;

for (int i = 0; i < m; i++) {

int a, b, c;

cin >> a >> b >> c;

point[a - 1].neighbor.insert({ &point[b - 1], c });

point[b - 1].degree++;

}

cin >> beginPoint >> endPoint;

extend();

if (point[endPoint - 1].distence < 0) cout << "No solution" << endl;

else cout << point[endPoint - 1].distence << endl;

}

Timus #1806. Mobile Telegraphs

题目：有n个数，每个数都由10个数字组成。并输入int costs[10];作为传递时间。每两个数之间要是有一位不同或有两位可以通过交换得到则这两个数可以互相传递，且传递时间为costs[有多少位相同的前缀]。输出从第一个数到最后一个数所要的最短时间。

解析：最短路径问题。记录两两之间的时间，用Dijkstra算法求解。

代码解析：
建议写代码前阅读以下条目
1. 存储数的方式可以是string，但是最好是long long，所占位数少，但对最终结果及是否通过没有太大关系。string好判断更简单，用long long判断比较烦，看个人喜好了。
2. 如果你卡在TLE(Time Limit Exceeded)8见此条。若用两个for循环依次记录相互之间的可达性会卡在Test 8。因为输入N非常大，导致超时。解决办法：建立所有数字/字符串的哈希表（map），改变每个数字一位/两位，看是否有相同的数字/字符串在输入中。因为哈希表的查找迅速，尽管改变次数多，但依旧比两个for循环来得快。
3. 如果你卡在WA(Wrong Answer)3见此条。你写的Dijkstra路径记录错误，Dijkstra算法是会更新路径，不是简单的输出此迭代得到的路径最短的点。
4. 如果你卡在WA8见此条。计算可达两点距离时出现错误，可能你写成了if(i == j)应写if(int(name[i] – ‘0’) == j)←对于储存形式为string来说。
5. 如果你卡在MLE(Memory Limit Exceeded)11见此条。在Dijkstra算法中只需要当前point相邻的点即可，并不需要全部的。最好不要在结构体中加入类似于unordered_map <Point*, int> neighbor;导致每个点都储存了可达点的数据，很容易造成内存溢出，并且没有这必要，造成内存浪费。记得new不用之后要delete。
7. 为了更加节省内存，你可以修改unordered_map <Point*, int> neighbor;为vector <int, int> neighbor;这样可能你放在结构体里面也不会MLE。
6. 推荐:
INF = 0x3f3f3f3f;
neighbor用unordered_map存储

#include<iostream>
#include<unordered_map>
#include<map>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f
using namespace std;

int costs[10];
int n;
vector<int>result;
map<long long, int>names;

struct Point
{
	Point(int i) {
		distence = INF;
		done = false;
		index = i;
	}
	long long name;
	Point* parent;
	long long distence;
	bool done;
	int index;
};

unordered_map<Point*, int>* neighbor;
vector<Point>point;

void cal_diff(Point* pointNow) {
	delete neighbor;
	neighbor = new unordered_map<Point*, int>;
	map<long long, int>::iterator ptr;
	long long name = pointNow->name;
	long long temp;
	for (int i = 0; i < 10; i++) {
		temp = name - name % long long(pow(10, i + 1)) / long long(pow(10, i)) * long long(pow(10, i)) - long long(pow(10, i));;
		for (int j = 0; j < 10; j++) {
			temp += long long(pow(10, i));
			if (temp == name)continue;
			ptr = names.find(temp);
			if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - i] });
		}
	}
	for (int i = 0; i < 10; i++) {
		int a = name % long long(pow(10, i + 1)) / long long(pow(10, i));
		for (int j = i + 1; j < 10; j++) {
			int b = name % long long(pow(10, j + 1)) / long long(pow(10, j));
			temp = name + long long(pow(10, i)) * (b - a) + long long(pow(10, j)) * (a - b);
			ptr = names.find(temp);
			if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - j] });
		}
	}
}

void dijkstra()
{
	set<pair<int, Point*>>queue;
	point[0].distence = 0;
	queue.insert(make_pair(0, &point[0]));
	Point* now;
	unordered_map<Point*, int>::iterator ptr;
	while (!queue.empty())
	{
		now = queue.begin()->second;
		if (now->index == n) return;
		queue.erase(queue.begin());
		if (now->done)
			continue;
		cal_diff(now);
		now->done = true;
		for (ptr = neighbor->begin(); ptr != neighbor->end(); ptr++) {
			Point* n = ptr->first;
			int cost = ptr->second;
			if (!n->done && n->distence > now->distence + cost) {
				n->parent = now;
				n->distence = now->distence + cost;
				queue.insert(make_pair(n->distence, n));
			}
		}
	}
}


void chaseBack() {
	result.push_back(n);
	Point* pointTemp = point[n - 1].parent;
	while (pointTemp != &point[0]) {
		result.insert(result.begin(), pointTemp->index);
		pointTemp = pointTemp->parent;
	}
	result.insert(result.begin(), 1);
}

int main() {
	cin >> n;
	for (int i = 0; i < 10; i++)cin >> costs[i];
	for (int i = 0; i < n; i++) {
		point.push_back(*new Point(i + 1));
		cin >> point[i].name;
		names.insert({ point[i].name, i });
	}
	dijkstra();
	if (point[n - 1].distence >= INF) cout << -1 << endl;
	else {
		chaseBack();
		cout << point[n - 1].distence << endl;
		cout << result.size() << endl;
		for (auto i : result)cout << i << " ";
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include<iostream>

#include<unordered_map>

#include<map>

#include<vector>

#include<set>

#define INF 0x3f3f3f3f

using namespace std;

int costs[10];

int n;

vector<int>result;

map<long long, int>names;

struct Point

{

Point(int i) {

distence = INF;

done = false;

index = i;

}

long long name;

Point* parent;

long long distence;

bool done;

int index;

};

unordered_map<Point*, int>* neighbor;

vector<Point>point;

void cal_diff(Point* pointNow) {

delete neighbor;

neighbor = new unordered_map<Point*, int>;

map<long long, int>::iterator ptr;

long long name = pointNow->name;

long long temp;

for (int i = 0; i < 10; i++) {

temp = name - name % long long(pow(10, i + 1)) / long long(pow(10, i)) * long long(pow(10, i)) - long long(pow(10, i));;

for (int j = 0; j < 10; j++) {

temp += long long(pow(10, i));

if (temp == name)continue;

ptr = names.find(temp);

if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - i] });

}

for (int i = 0; i < 10; i++) {

int a = name % long long(pow(10, i + 1)) / long long(pow(10, i));

for (int j = i + 1; j < 10; j++) {

int b = name % long long(pow(10, j + 1)) / long long(pow(10, j));

temp = name + long long(pow(10, i)) * (b - a) + long long(pow(10, j)) * (a - b);

ptr = names.find(temp);

if (ptr != names.end()) (*neighbor).insert({ &point[ptr->second], costs[9 - j] });

}

void dijkstra()

{

set<pair<int, Point*>>queue;

point[0].distence = 0;

queue.insert(make_pair(0, &point[0]));

Point* now;

unordered_map<Point*, int>::iterator ptr;

while (!queue.empty())

{

now = queue.begin()->second;

if (now->index == n) return;

queue.erase(queue.begin());

if (now->done)

continue;

cal_diff(now);

now->done = true;

for (ptr = neighbor->begin(); ptr != neighbor->end(); ptr++) {

Point* n = ptr->first;

int cost = ptr->second;

if (!n->done && n->distence > now->distence + cost) {

n->parent = now;

n->distence = now->distence + cost;

queue.insert(make_pair(n->distence, n));

}

void chaseBack() {

result.push_back(n);

Point* pointTemp = point[n - 1].parent;

while (pointTemp != &point[0]) {

result.insert(result.begin(), pointTemp->index);

pointTemp = pointTemp->parent;

}

result.insert(result.begin(), 1);

}

int main() {

cin >> n;

for (int i = 0; i < 10; i++)cin >> costs[i];

for (int i = 0; i < n; i++) {

point.push_back(*new Point(i + 1));

cin >> point[i].name;

names.insert({ point[i].name, i });

}

dijkstra();

if (point[n - 1].distence >= INF) cout << -1 << endl;

else {

chaseBack();

cout << point[n - 1].distence << endl;

cout << result.size() << endl;

for (auto i : result)cout << i << " ";

}

Timus #1080. Map Coloring

题目：有k行，每行包含第i个点相邻的点。现有0/1两种颜色，相邻的颜色必须不一样，如果能进行涂色，输出每个点的颜色，如果不能进行涂色，则输出-1。

解析：
1. BFS
2. 我没用那么高级的方法，就只用vector迭代涂色。

#include<iostream>
#include<vector>
#include<map>
#include<set>
using namespace std;

vector<vector<int>>connection;
vector<pair<int, int>>color;
set<int>finish;

int coloring(vector<int> &singleConnection, int colorNow, int point) {
	set<int>::iterator ptr;
	ptr = finish.find(point);
	finish.erase(ptr);
	int colorTemp;
	for (int i = 0; i < singleConnection.size(); i++) {
		colorTemp = color[singleConnection[i]].second;
		if (colorTemp == -1) {
			color[singleConnection[i]].second = 1 - colorNow;
			int error = coloring(connection[singleConnection[i]], 1 - colorNow, singleConnection[i]);
			if (error == -1)return -1;
		}
		else if(colorNow == colorTemp) {
			return -1;
		}
	}
	return 0;
}

int main() {
	int n, temp;
	cin >> n;
	for (int i = 0; i < n; i++) {
		vector<int>connectTemp;
		connection.push_back(connectTemp);
	}
	for (int i = 0; i < n; i++) {
		color.push_back(make_pair(i, -1));
		finish.insert(i);
		while (1) {
			cin >> temp;
			if (temp != 0) { 
				connection[i].push_back(temp - 1); 
				connection[temp - 1].push_back(i);
			}
			else break;
		}
	}
	while (!finish.empty()) {
		color[*finish.begin()].second = 0;
		int error = coloring(connection[*finish.begin()], 0, *finish.begin());
		if(error == -1) {
			cout << -1 << endl;
			return 0;
		}
	}
	for (auto i : color)cout << i.second;
}

#include<iostream>

#include<vector>

#include<map>

#include<set>

using namespace std;

vector<vector<int>>connection;

vector<pair<int, int>>color;

set<int>finish;

int coloring(vector<int> &singleConnection, int colorNow, int point) {

set<int>::iterator ptr;

ptr = finish.find(point);

finish.erase(ptr);

int colorTemp;

for (int i = 0; i < singleConnection.size(); i++) {

colorTemp = color[singleConnection[i]].second;

if (colorTemp == -1) {

color[singleConnection[i]].second = 1 - colorNow;

int error = coloring(connection[singleConnection[i]], 1 - colorNow, singleConnection[i]);

if (error == -1)return -1;

}

else if(colorNow == colorTemp) {

return -1;

}

return 0;

}

int main() {

int n, temp;

cin >> n;

for (int i = 0; i < n; i++) {

vector<int>connectTemp;

connection.push_back(connectTemp);

}

for (int i = 0; i < n; i++) {

color.push_back(make_pair(i, -1));

finish.insert(i);

while (1) {

cin >> temp;

if (temp != 0) {

connection[i].push_back(temp - 1);

connection[temp - 1].push_back(i);

}

else break;

}

while (!finish.empty()) {

color[*finish.begin()].second = 0;

int error = coloring(connection[*finish.begin()], 0, *finish.begin());

if(error == -1) {

cout << -1 << endl;

return 0;

}

for (auto i : color)cout << i.second;

}