网页设计素材网站集/百度推广咨询

马上要复试了兄弟们，加油加油。

今天开始学习图论经典算法-最小生成树。给一个无向带权图，找到连通所有点且权值最小的子图。有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));}
}

。