机试准备第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));
        
    }
}

。