OJ上面关于图的一些题目

OJ上面关于图的一些题目

Scroll Down

D.紧急救援

#include<iostream>
#include<cstdio>
#include<string.h>
#define MAX 250
using namespace std;
int graph[MAX][MAX];
int vertex[MAX];
int M, N;
int sum;
void dfs(int start) {
    sum++;
    vertex[start] = 1;
    for(int j = 0; j < M; j++) {
        if(vertex[j] == 0 && graph[start][j] == 1) {
            dfs(j);
        }
    }
}
int main() {
    int index = 1;
    int a, b;
    while(cin >> M >> N) {
        if(M == 0 && N == 0) {
            break;
        }
        sum = 0;
        memset(graph, 0, sizeof(graph));
        memset(vertex, 0, sizeof(vertex));
        for(int i = 0; i < N; i++) {
            cin >> a >> b;
            graph[a - 1][b - 1] = 1;
            graph[b - 1][a - 1] = 1;
        }

        int icount = 0;
        for(int i = 0; i < M; i++) {
            if(vertex[i] == 0) {
                dfs(i);
                if(sum > 2) {
                    icount += 2;
                } else {
                    icount += 1;
                }
                sum = 0;
            }
        }
        printf("Case #%d:至少需要%d架直升机救援\n", index++, icount);
    }
}
#include<iostream>
#include<queue>
#include<string.h>
#define MAX 150
using namespace std;
int id[MAX], tr[MAX];
int M, N;
int find(int p) {
    while(p != id[p]) {
        p = id[p];
    }
    return p;
}
void Union(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);
    if(pRoot != qRoot) {
        id[qRoot] = pRoot;
    }
}
void count() {
    int count = 1, plane_count = 1;
    for(int i = 1; i < M; i++) {
        if(tr[i] == tr[i - 1]) {
            count++;
        } else {
            if(count >= 3) {
                plane_count += 2;
            } else {
                plane_count += 1;
            }
            count = 0;
        }
    }
    cout << "至少需要" << plane_count << "架直升机救援" << endl;
}
int main() {
    int a, b;
    int index = 1;
    while(cin >> M >> N) {
        if(M == 0 && N == 0) {
            break;
        }
        for(int i = 0; i < M; i++) {
            id[i] = i;
        }
        for(int i = 0; i < N; i++) {
            cin >> a >> b;
            Union(a - 1, b - 1);
        }
        for(int i = 0; i < M; i++) {
            tr[i] = find(i);
        }
        cout << "Case #" << (index++) << ":";
        count();
    }
}

F.图的深度优先搜索

#include<iostream>
#include<string.h>
#define MAX 250
using namespace std;
int graph[MAX][MAX];
int vertex[MAX];
int M, N;
void dfs(int start) {
    vertex[start] = 1;
    cout << (char)(start + 65);
    for(int j = 0; j < M; j++) {
        if(vertex[j] == 0 && graph[start][j] == 1) {
            dfs(j);
        }
    }
}
int main() {
    int index = 1;
    char a, b;
    while(cin >> M >> N) {
        if(M == 0 && N == 0) {
            break;
        }
        memset(graph, 0 , sizeof(graph));
        memset(vertex, 0 , sizeof(vertex));
        for(int i = 0; i < N; i++) {
            cin >> a >> b;
            graph[a - 65][b - 65] = 1;
            graph[b - 65][a - 65] = 1;
        }
        dfs(0);
        cout << endl;
    }
}

G.图的广度优先搜索

#include<iostream>
#include<queue>
#include<string.h>
#define MAX 250
using namespace std;
int graph[MAX][MAX];
int vertex[MAX];
int M, N;
void bfs(int start) {
    queue<int> q;
    q.push(start);
    vertex[start] = 0;
    while(!q.empty()) {
        int ver = q.front();
        q.pop();
        cout << (char)(ver + 65);
        for(int i = ver; i < M; i++) {
            if(vertex[i] == 0 && graph[ver][i] == 1) {
                q.push(i);
                vertex[i] = 1;
            }
        }
    }
}
int main() {
    int index = 1;
    char a, b;
    while(cin >> M >> N) {
        if(M == 0 && N == 0) {
            break;
        }
        memset(graph, 0 , sizeof(graph));
        memset(vertex, 0 , sizeof(vertex));
        for(int i = 0; i < N; i++) {
            cin >> a >> b;
            graph[a - 65][b - 65] = 1;
            graph[b - 65][a - 65] = 1;
        }
        bfs(0);
        cout << endl;
     }
}

H.图的连通性

#include<iostream>
#include<queue>
#include<string.h>
#define MAX 150
using namespace std;
int id[MAX], tr[MAX];
int M, N;
int find(int p) {
    while(p != id[p]) {
        p = id[p];
    }
    return p;
}
void Union(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);
    if(pRoot != qRoot) {
        id[qRoot] = pRoot;
    }
}
bool IsConnectedGraph() {
    for(int i = i; i < M; i++) {
        if(tr[i] != tr[i - 1]) {
            return false;
        }
    }
    return true;
}
int main() {
    int a, b;
    int index = 1;
    while(cin >> M >> N) {
        if(M == 0 && N == 0) {
            break;
        }
        for(int i = 0; i < M; i++) {
            id[i] = i;
        }
        for(int i = 0; i < N; i++) {
            cin >> a >> b;
            Union(a - 1, b - 1);
        }
        for(int i = 0; i < M; i++) {
            tr[i] = find(i);
        }
        if(IsConnectedGraph()) {
            cout <<"Connected graph"<< endl;
        } else {
            cout <<"Unconnected graph"<< endl;
        }
    }
}

I. 光缆的铺设

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<vector>
#include<string.h>
#define MAX 1000
using namespace std;
int id[MAX];
int V, E;
struct Edge {
    int v, w, weight;
    friend bool operator < (const Edge a , const Edge b){
        return a.weight > b.weight;
    }
};
bool cmp(Edge a, Edge b) {
    return a.v - b.v < 0;
}
int find(int p) {
    while(p != id[p]) {
        p = id[p];
    }
    return p;
}
bool connected(int p, int q) {
    return find(p) == find(q);
}
void Union(int p, int q) {
    int x = find(p);
    int y = find(q);
    if(x != y) {
        id[x] = y;
    }
}
void Kruskal(priority_queue<Edge> &q, vector<Edge> &v) {
    while(!q.empty() && v.size() < (V - 1)) {
        Edge e = q.top();
        q.pop();
        if(!connected(e.v, e.w)) {
            Union(e.v, e.w);
            v.push_back(e);
        }
    }
}
void print(vector<Edge> &v) {
    int weight = 0;
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < v.size(); i++) {
        printf("%d-%d-%d,", v.at(i).v, v.at(i).w, v.at(i).weight);
        weight += v.at(i).weight;
    }
    printf("总长度是%d\n", weight);
}
int main() {
    int a, b, weight;
    int index = 1;
    while(cin >> V >> E) {
        if(V == 0 && E == 0) {
            break;
        }
        for(int i = 0; i < V; i++) {
            id[i] = i;
        }
        priority_queue<Edge> q;
        vector<Edge> v;
        for(int i = 0; i < E; i++) {
            cin >> a >> b >> weight;
            Edge e;
            e.v = a;e.w = b;e.weight = weight;
            q.push(e);
        }
        Kruskal(q, v);
        printf("case %d:", index++);
        print(v);
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int index = 1;
        while (sc.hasNext()) {
            int V = sc.nextInt();
            int E = sc.nextInt();
            if (V == 0 && E == 0) {
                break;
            }
            EdgeWeightedGraph edgeWeightedGraph = new EdgeWeightedGraph(V);
            for (int i = 0; i < E; i++) {
                Edge e = new Edge(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
                edgeWeightedGraph.addEdge(e);
            }
            KruskalMST kruskal = new KruskalMST();
            System.out.print("case " + (index++) + ":");
            kruskal.kruskalMST(edgeWeightedGraph);
        }
    }
}

/*
 * 图中的边
 */
class Edge implements Comparable<Edge> {
    private final int v;
    private final int w;
    private int weight;

    public Edge(int v, int w, int weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public int either() {
        return v;
    }

    public int other(int vertex) {
        if (vertex == v) {
            return w;
        } else {
            return v;
        }
    }

    public int getWeight() {
        return weight;
    }

    @Override
    public int compareTo(Edge o) {
        if (this.weight > o.weight) {
            return 1;
        } else if (this.weight < o.weight) {
            return -1;
        } else {
            return 1;
        }
    }

    @Override
    public String toString() {
        return "Edge{" + "v=" + v + ", w=" + w + ", weight=" + weight + '}';
    }
}

class UF {
    private int[] id;
    private int count;

    public UF(int N) {
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }

    public int count() {
        return count;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        id[pRoot] = qRoot;
        count--;
    }
}

/*
 * 无向连通图的数据类型
 */
class EdgeWeightedGraph {
    private final int V;
    private int E;
    private LinkedList<Edge>[] adj;

    public EdgeWeightedGraph(int V) {
        this.V = V;
        this.E = 0;
        this.adj = (LinkedList<Edge>[]) new LinkedList[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new LinkedList<Edge>();
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(Edge e) {
        int v = e.either();
        int w = e.other(v);
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }

    public LinkedList<Edge> edges() {
        LinkedList<Edge> b = new LinkedList<Edge>();
        for (int v = 0; v < V; v++) {
            for (Edge e : adj[v]) {
                if (e.other(v) > v) {
                    b.add(e);
                }
            }
        }
        return b;
    }

    public Iterable<Edge> adj(int v) {
        return adj[v];
    }
}

class KruskalMST {
    private Queue<Edge> mst; // 存储最小生成树的每条边
    private Queue<Edge> pq; // 优先队列,获取权重最小的边
    private int weight; // 权重和

    public KruskalMST() {
    }

    public void kruskalMST(EdgeWeightedGraph G) {
        mst = new LinkedList<Edge>();
        pq = new PriorityQueue<Edge>();
        for (Edge e : G.edges()) {
            pq.offer(e);
        }
        UF uf = new UF(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.poll(); // 从pq中获得权重最小的边和它的顶点
            int v = e.either();
            int w = e.other(v);
            if (!uf.connected(v, w)) { // 如果v和w不构成环
                uf.union(v, w); // 合并分量
                mst.offer(e); // 将边添加到最小生成树中
            }
        }
        printKruskalMST();
    }

    private void printKruskalMST() {
        ArrayList<Edge> list = new ArrayList<Edge>();
        while (!mst.isEmpty()) {
            Edge e = mst.poll();
            weight += e.getWeight();
            list.add(e);
        }
        Collections.sort(list, new Comparator<Edge>() {

            @Override
            public int compare(Edge o1, Edge o2) {
                if (o1.either() > o2.either()) {
                    return 1;
                } else if (o1.either() < o2.either()) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

        for (int i = 0; i < list.size(); i++) {
            int v = list.get(i).either();
            int w = list.get(i).other(v);
            System.out.print((v + 1) + "-" + (w + 1) + "-" + list.get(i).getWeight() + ",");
        }
        System.out.println("总长度是" + weight);
    }
}

J. 泥坑

#include<iostream>
#include<string.h>
#include<algorithm>
#define MAX 1000
using namespace std;
int map[MAX][MAX];
int m, n;
int icount, imax;
int load[8][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
void dfs(int x, int y) {
    icount++;
    map[x][y] = 0;
    for(int i = 0; i < 8; i++) {
        int nextX = x + load[i][0];
        int nextY = y + load[i][1];
        if(nextX < m && nextX >= 0 && nextY < n && nextY >= 0 && map[nextX][nextY] == 1) {
            dfs(nextX, nextY);
        }
    }
}
int main() {
    while(cin >> m >> n) {
        icount = 0;
        imax = 0;
        memset(map, 0, sizeof(map));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j] == 1) {
                    dfs(i, j);
                    imax = max(imax, icount);
                    icount = 0;
                }
            }
        }
        cout << imax << endl;
    }
}
支付宝 微信