机试准备第18天
马上要复试了兄弟们,加油加油。
今天开始学习图论经典算法-最小生成树。给一个无向带权图,找到连通所有点且权值最小的子图。有prim算法与kruskal算法,只需要掌握kruskal算法,适用于稀疏图。首先将所有的边按权排序,按权从小到大的顺序加入子图,如果边的两点已经连通,则不加入。直到边数=顶点数减一即可退出。
第一题是还是畅通工程。
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int father[100];
int Find(int u) { //判断连通
if (u == father[u]) return u;
else {
father[u] = Find(father[u]);
return father[u];
}
}
void Union(int u, int v) {
int uroot = Find(u);
int vroot = Find(v);
father[vroot] = uroot;
}
struct road {
int frist;
int second;
int cost;
};
bool cmp(road left, road right) {
if (left.cost < right.cost) return true;
else return false;
}
int main() {
int N;
while (scanf("%d", &N) != EOF) {
if (N == 0) break;
for (int i = 1; i <= N; i++) {
father[i] = i;
}
vector<road> rod;
for (int i = 0; i < N * (N - 1) / 2; i++) { //读入所有的路径信息
road val;
scanf("%d%d%d", &val.frist, &val.second, &val.cost);
rod.push_back(val);
}
sort(rod.begin(), rod.end(), cmp);
int biannum = 0;
int allcost = 0;
for (int i = 0; i < rod.size(); i++) {
if (biannum == N - 1) break;
int a1 = Find(rod[i].frist);
int a2 = Find(rod[i].second);
if (a1 != a2) { //两村庄此时不连通
Union(rod[i].frist, rod[i].second);
biannum++;
allcost += rod[i].cost;
}
}
printf("%d\n", allcost);
}
}
第二题是继续畅通工程。
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int father[100];
struct Road {
int u;
int v;
int cost;
int isconnect;
};
bool cmp(Road left, Road right) {
if (left.isconnect > right.isconnect) return true;
else if (left.isconnect == right.isconnect &&
left.cost < right.cost) return true;
else return false;
}
int find(int u) {
if (u == father[u]) return u;
else {
father[u] = find(father[u]);
return father[u];
}
}
void Union(int u, int v) {
int uroot = find(u);
int vroot = find(v);
father[vroot] = uroot;
}
int main() {
int n;
while (scanf("%d", &n) != EOF) {
if (n == 0) break;
for (int i = 1; i <= n; i++) {
father[i] = i;
}
vector<Road> roadVec;
for (int i = 0; i < n * (n - 1) / 2; i++) {
Road val;
scanf("%d%d%d%d", &val.u, &val.v, &val.cost, &val.isconnect);
roadVec.push_back(val);
}
sort(roadVec.begin(), roadVec.end(), cmp);
int edgenum = 0;
int costnum = 0;
for (int i = 0; i < roadVec.size(); i++) {
if (edgenum == n - 1) break;
if (find(roadVec[i].u) != find(roadVec[i].v)) { //未连通
Union(roadVec[i].u, roadVec[i].v);
edgenum++;
if (roadVec[i].isconnect == 0) costnum += roadVec[i].cost;
}
}
printf("%d\n", costnum);
}
}
第三题是roads,怎么这么爱英文题。
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int father[30];
struct road {
int u;
int v;
int cost;
};
bool cmp(road left, road right) {
if (left.cost < right.cost) return true;
else return false;
}
int find(int u) {
if (u == father[u]) return u;
else {
father[u] = find(father[u]);
return father[u];
}
}
void Union(int u, int v) {
int uroot = find(u);
int vroot = find(v);
father[vroot] = uroot;
}
int main() {
int n;
while (scanf("%d", &n) != EOF) {
if (n == 0) break;
vector<road> roadVec;
for (int i = 0; i < n; i++) {
father[i] = i;//chushihua
}
for (int i = 0; i < (n - 1); i++) {
char first;
scanf(" %c", &first);
int num;
scanf("%d", &num);
for (int j = 0; j < num; j++) {
char second;
int cost;
scanf(" %c", &second);
scanf("%d", &cost);
road val;
val.u = first - 'A';
val.v = second - 'A';
val.cost = cost;
roadVec.push_back(val);
}
}
sort(roadVec.begin(), roadVec.end(), cmp);
int edgenum = 0;
int allcost = 0;
for (int i = 0; i < roadVec.size(); i++) {
if (edgenum == n - 1) break;
if (find(roadVec[i].u) != find(roadVec[i].v)) {
Union(roadVec[i].u, roadVec[i].v);
edgenum++;
allcost += roadVec[i].cost;
}
}
printf("%d\n", allcost);
}
}
第四题是雀斑数量。简单的kruskal算法应用。
#include <stdio.h>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int father[100];
struct Point {
float x;
float y;
};
struct Road {
int u;
int v;
float dis;
};
bool cmp(Road left, Road right) {
if (left.dis < right.dis) return true;
else return false;
}
int find(int u) {
if (u == father[u]) return u;
else {
father[u] = find(father[u]);
return father[u];
}
}
void Union(int u, int v) {
int uroot = find(u);
int vroot = find(v);
father[vroot] = uroot;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
father[i] = i;
}
vector<Point> pointVec(n + 1);
for (int i = 1; i <= n; i++) { //读入所有坐标位置
Point a;
scanf("%f%f", &a.x, &a.y);
pointVec[i] = a;
}
vector<Road> roadVec;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
Road road1;
road1.u = i;
road1.v = j;
road1.dis = sqrt((pointVec[i].x - pointVec[j].x) * (pointVec[i].x -
pointVec[j].x)
+ (pointVec[i].y - pointVec[j].y) * (pointVec[i].y - pointVec[j].y));
roadVec.push_back(road1);
}
}
sort(roadVec.begin(), roadVec.end(), cmp);
int edgesize = 0;
float length = 0;
for (int i = 0; i < roadVec.size(); i++) {
if (edgesize == n - 1) break;
if (find(roadVec[i].u) != find(roadVec[i].v)) {
Union(roadVec[i].u, roadVec[i].v);
edgesize++;
length += roadVec[i].dis;
}
}
printf("%.2f", length);
}
下面学习单源最短路径djkstra算法。用于解决从一个顶点到其他所有顶点的带权路径。取出一个点作为当前节点,更新当前节点的邻居到起点的距离,找到离起点最近的点,将其更新为当前节点。BFS+贪心。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct Edge{//边节点信息
int u;
int v;
int weight;
};
vector<Edge> graph[300];//邻接表
struct PQueueNode{//各点离起点的距离
int u;
int dis;
};
bool operator < (PQueueNode left, PQueueNode right){
if(left.dis > right.dis) return true;
else return false;
}
int Dijkstra(int s, int t){
priority_queue<PQueueNode> pqueue;//top放的是距离最小的节点
int distance[300];
bool isvisited[300];
for(int i = 0;i<300;i++){
distance[i] = -1;//-1代表正无穷
isvisited[i] = false;
}
distance[s] = 0;
PQueueNode qnode;
qnode.u = s;
qnode.dis = 0;
pqueue.push(qnode);
while(!pqueue.empty()){
int u = pqueue.top().u;//距离起点最近的当前节点
pqueue.pop();
if(isvisited[u] == true){
continue;
}
isvisited[u] = true;
for(int i = 0; i <graph[u].size();i++){
int v = graph[u][i].v;
int weight = graph[u][i].weight;
if(distance[v] == -1||distance[v] > distance[u]+weight){
distance[v] = distance[u]+weight;//更新
PQueueNode newnode;
newnode.u = v;
newnode.dis = distance[v];
pqueue.push(newnode);
}
}
}
return distance[t];
}
int main(){
int n,m;
while(scanf("%d%d", &n, &m)!=EOF){
for(int i = 0; i< n;i++){
graph[i].clear();
}
for(int i = 0; i<m;i++){//读入m条边
int u, v, weight;
scanf("%d%d%d", &u, &v, &weight);
Edge e1;
e1.u = u;
e1.v = v;
e1.weight = weight;
graph[u].push_back(e1);
Edge e2;
e2.u = v;
e2.v = u;
e2.weight = weight;
graph[v].push_back(e2);//邻接表已完成
}
int s,t;
scanf("%d%d", &s, &t);
printf("%d\n", Dijkstra(s, t));
}
}
。