头像

锤子科技未来产品经理


访客:312

离线:2小时前



链式前向星存储边

1. 用一个node结构体来存储每一条边的信息,int v,w,pre; 
   其中v是这条边的终点,w是这条边的权重,而最重要的是pre,
   存的是与这一条边同一个起点的上一条边的序号

2. 另外还有一个p[n]的数组,其中p[i]来保存第i个点的最后一条
   边的序号。所以到时候遍历边的时候是倒序遍历。

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAX 10000000
int nEdge;//代表的是输入边的总数
int p[MAX];//p[i]保存的是连接第i个点的最后一条边的序号。

struct node
{
    int v,w,pre;//pre保存的是上一条边的序号(输入时的序号)
} e[MAX];

void addEdge(int u,int v,int w)//把u->v权重为w的边加入到边集。
{
    nEdge++;//新增了一条u->v的边,此时这条边的序号是nEdge;
    e[nEdge].v = v;
    e[nEdge].w = w;
    e[nEdge].pre = p[u];//连接u点这条边的上一条边的序号是p[u];
    p[u] = nEdge;//连接u点又新增了一条边,这条边的序号是nEdge;
}

int main()
{
    int n,m;//n个点,m条边
    int a,b,c;
    while(~scanf("%d%d",&n,&m))
    {
        memset(p,0,sizeof(p));
        //初始化连接每个点的边的序号都是0,因为这个时候还没有边
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            //a点到b点权重为c的边
            addEdge(a,b,c);
            //有向图,所以a->b,只是a到b,b不能到a;
            //addEdge(b,a,c);如果是无向图,就加上这一句,添加b->a的边
        }
        //输出边,一共有n个点,把从这个点出发的边分别输出出来。
        for(int i = 1; i <= n; i++) 
        {
            printf("第%d个点:\n",i);
            //遍历从i点出发的边的时候,是从最后一条边开始遍历,直到第一条边
            for(int j = p[i]; j; j = e[j].pre) 
            {
                printf("%d->%d,权重:%d\n",i,e[j].v,e[j].w);
            }
        }
    }
    return 0;
}

代码作者:optimjie

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c; 
    // 有重边也不要紧,假设1->2有权重为2和3的边,再遍历到点1的时候
    //2号点的距离会更新两次放入堆中
    e[idx] = y; 
    // 这样堆中会有很多冗余的点,但是在弹出的时候还是会弹出最小值
    //2+x(x为之前确定的最短路径)
    ne[idx] = h[x]; 
    // 标记st为true,所以下一次弹出3+x会continue不会向下执行。
    h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 1;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢,
    // 首先小根堆是根据距离来排的,所以有一个变量要是距离,其次在从堆中拿出来的时    
    // 候要知道知道这个点是哪个点,不然怎么更新邻接点呢?所以第二个变量要存点。
    heap.push({ 0, 1 }); 
    // 这个顺序不能倒,pair排序时是先根据first,再根据second,这里显然要根据距离排序
    while(heap.size())
    {
        PII k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = k.second, distance = k.first;

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标,e中在存的是i这个下标对应的点。
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dijkstra() << endl;

    return 0;
}




java 代码 (参考了其他同学的,写一个题解以后复习用)

class Solution {
    public int[] printMatrix(int[][] matrix) {
        int row = matrix.length;
        int[] r = new int[0];
        if(row==0)
            return r;
        int col = matrix[0].length;
        if(col==0)
            return r;

        int i=0; int j=0;
        int a=row-1; int b=col-1;
        int[] re = new int[row*col];
        int count=0;

        while(i<=a||j<=b){
            for(int t = j; t <= b; t++)//向右
                if(matrix[i][t]!=Integer.MIN_VALUE){
                    re[count]=matrix[i][t];
                    count++;
                    matrix[i][t]=Integer.MIN_VALUE;
                }

            for(int s = i+1; s <= a; s++)//向下
                if(matrix[s][b]!=Integer.MIN_VALUE){
                    re[count]=matrix[s][b];
                    count++;
                    matrix[s][b]=Integer.MIN_VALUE;
                }

            for(int t = b-1; t>=j; t--)//向左
                if(matrix[a][t]!=Integer.MIN_VALUE){
                    re[count]=matrix[a][t];
                    count++;
                    matrix[a][t]=Integer.MIN_VALUE;
                }

            for(int s = a-1; s>i; s--)//向上
                if(matrix[s][j]!=Integer.MIN_VALUE){
                    re[count]=matrix[s][j];
                    count++;
                    matrix[s][j]=Integer.MIN_VALUE;
                }

            i++;j++;
            a--;b--;
            if(a<0||b<0)
                break;
        }
        return re;
    }
}



利用java的API对数组中的数字组合进行排序

java 代码

class Solution {
    public String printMinNumber(int[] nums) {
        IntStream stream = Arrays.stream(nums);
        Stream<Integer> integerStream = stream.boxed();
        Integer[] integers = integerStream.toArray(Integer[]::new);
        return mysort(integers);
    }

    private String mysort(Integer[] arr)
    {
        Arrays.sort(arr, new Comparator<Integer>(){
           public int compare(Integer a1, Integer a2) 
           {
               String s1 = a1 + "" + a2;
               String s2 = a2 + "" + a1;
               return s1.compareTo(s2);
           }
        });

        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < arr.length; i++) sb.append(arr[i]);
        return sb.toString();
    }
}



堆排序 C++ 代码

class Solution {
public:
    int size = 0, num = 0;
    vector<int> heap;
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        heap = vector<int>(k);
        num = k;
        for(int i = 0; i < (int)input.size(); i++)
        {
            heapSort(input[i]);
        }

        sort(heap.begin(), heap.end());
        cout << heap.size() << endl;
        return heap;
    }

    void heapSort(int x)
    {
        if(size < num)
        {
            heap[size++] = x;
            if(size == num)
            {
                makeMinHeap(heap);
                size++;
            }
        }
        else if(heap[0] > x)
        {
            heap[0] = x;
            minHeapDown(heap, 0, num);
        }
    }

    void makeMinHeap(vector<int>& A)
    {
       int n = A.size();
       for(int i = n / 2 - 1; i >= 0; i--) 
            minHeapDown(A, i, n);
    }

    //维护一个大顶堆,堆中最大的元素在第一个
    void minHeapDown(vector<int>& A, int i, int n)
    {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if(left > n) return;
        int max = left;
        if(right >= n)
            max = left;
        else
        {
            if(A[right] > A[left])
                max = right;
        }
        if(A[i] >= A[max])
            return;
        swap(A[i], A[max]);
        minHeapDown(A, max, n);
    }

};



C++ 代码

#include <iostream>
#include <climits>
#include <cstring>
using namespace std;

const int N = 510;

int graph[N][N];
int dist[N];
bool visited[N];

int n, m;

int dijkstra(int n)
{
    memset(dist, 0x3f, sizeof dist);
    memset(visited, false, sizeof visited);

    dist[1] = 0;

    for(int i = 1; i <= n; i++)
    {
        int curPoint = -1;
        int curPath = INT_MAX;
        for(int j = 1; j <= n; j++)
        {
            //找到到第一个点的最短距离
            if(!visited[j] && dist[j] < curPath)
            {
                curPath = dist[j];
                curPoint = j;
            }
        }

        visited[curPoint] = true;

        //更新距离表
        for(int i = 1; i <= n; i++)
        {
            if(!visited[i])
            dist[i] = min(dist[i], (curPath + graph[curPoint][i]));
        }

    }

    if(dist[n] == 0x3f3f3f3f)
        return -1;
    return dist[n];
}


int main()
{

    int x, y, z;
    cin >> n >> m;

    //初始化最大值不可以用INT_MAX
    memset(graph, 0x3f, sizeof graph);

    for(int i  = 0; i < m; i++)
    {
        cin >> x >> y >> z;
        graph[x][y] = min(graph[x][y], z);
    }

    cout << dijkstra(n) << endl;

    return 0;

}



实在是太难了,等水平高的一点再回来看看 C++ 代码

//剪枝方法
//1.优化搜索顺序(从选择少的地方开始) 2.排除重复信息 3.可行性剪枝 4.最优性剪枝

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 9;

int row[N], col[N], cell[3][3];
char str[100];

//ones 存储每一个数字中有多少个1
int ones[1 << N], map[1 << N];

inline int lowbit(int x)
{
    return x & -x;
}

void init()
{
    for(int i = 0 ; i < N; i++) row[i] = col[i] = (1 << N) - 1;
    for(int i = 0 ; i < 3; i++)
        for(int j = 0; j < 3; j++)
            cell[i][j] = (1 << N) - 1;
}


inline int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
    if(!cnt) return true;

    //寻找方案数最小的位置
    int minv = 10;
    int x, y;
    for(int i = 0 ; i < N; i++)
        for(int j = 0 ; j < N; j++)
            if(str[i * 9 + j] == '.')
            {
                int t = ones[get(i, j)];
                if(t < minv)
                {
                    minv = t;
                    x = i;
                    y = j;
                }
            }

    for(int i = get(x, y); i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];
        row[x] -= 1 << t;
        col[y] -= 1 << t;
        cell[x / 3][y / 3] -= 1 << t;
        str[x * 9 + y] = '1' + t;

        if(dfs(cnt - 1)) return true;

        row[x] += 1 << t;
        col[y] += 1 << t;
        cell[x / 3][y / 3] += 1 << t;
        str[x * 9 + y] = '.';

    }


    return false;
}



int main()
{

    //map和one 进行优化剪枝用下标对应所填数值,初始所有位当置1
    for(int i=0;i<N;i++) map[1<<i]=i; //最低位的1是在第几位

    //统计第i位可选的方案数
    for(int i=0;i<1<<N;i++){
       int s=0;
       for(int j=i;j;j-=lowbit(j)) s++;  //统计第i个位置可选的方案数
       ones[i]=s;
    } 


    while(cin >> str, str[0] != 'e')
    {
        init();

        int cnt = 0;
        for(int i = 0, k = 0; i < N; i ++)
            for(int j = 0; j < N; j ++, k ++)
                if(str[k] != '.')
                {
                    int t = str[k] - '1';
                    row[i] -= 1 << t;
                    col[j] -= 1 << t;
                    cell[i / 3][j / 3] -= 1 << t;
                }
                else cnt ++;
        dfs(cnt);

        cout << str << endl;

    }

    return 0;
}




两个地方可以剪枝 1.将猫的重量从大到小排序 2.如果方案比现有方案需要的车的数量多就直接放弃

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
//猫的重量 每辆车现在的重量
int cat[N], sum[N];
int ans = N;
int m, n;

// 猫、车
void dfs(int u, int k)
{
    if(k >= ans) return;

    if(u == n)
    {
        ans = k;
        return;
    }

    for(int i = 0; i < k; i++)
    {
        if(cat[u] + sum[i] <= m)
        {
            sum[i] += cat[u];
            dfs(u + 1, k);
            sum[i] -= cat[u];
        }
    }

    sum[k] = cat[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;
}


int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        cin >> cat[i];

    //先考虑体重大的猫,选择比较少
    sort(cat, cat + n);
    reverse(cat, cat + n);

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}




对符合条件的状态的判断比较困难 C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 366;

int n;
//天,坐标,四个角没有下雨的天数
//bfs防止向回搜索可以通过bool或者在寻找最短路径的时候通过更改数组的值来实现
bool st[N][3][3][7][7][7][7];
struct Node
{
    int day, x, y, s0, s1, s2, s3;
};
//每天个过节情况
int state[N][4][4];

int bfs()
{
    //如果第一天就不可以下雨,直接返回
    if(state[1][1][1] || state[1][1][2] || state[1][2][1] || state[1][2][2]) return 0;
    queue<Node> q;
    memset(st, 0, sizeof st);
    //第一天云在中心所有四个角的区域都没有下雨
    q.push({1,1,1,1,1,1,1});
    st[1][1][1][1][1][1][1] = true;

    int dx[] = {-1, 0, 1, 0, 0};
    int dy[] = {0, 1, 0, -1, 0};

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        if(t.day == n)
            return 1;

        //每一个方向可以走一步或者两步
        for(int i = 0 ; i < 5; i++)
            for(int j = 1; j <= 2; j++)
            {
                int x = t.x + dx[i] * j;
                int y = t.y + dy[i] * j;
                if(x < 0 || x >= 3 || y < 0 || y >= 3) continue;

                auto &s = state[t.day + 1];
                if(s[x][y] || s[x][y + 1] || s[x + 1][y + 1] || s[x + 1][y]) continue;

                int s0 = t.s0, s1 = t.s1, s2 = t.s2, s3 = t.s3;
                if(!x && !y) s0 = 0;
                else if( ++ s0 == 7) continue;
                if(!x && y == 2) s1 = 0;
                else if( ++ s1 == 7) continue;
                if(x == 2 && !y) s2 = 0;
                else if( ++ s2 == 7) continue;
                if(x == 2 && y == 2) s3 = 0;
                else if( ++ s3 == 7) continue;

                if(st[t.day + 1][x][y][s0][s1][s2][s3]) continue;

                st[t.day + 1][x][y][s0][s1][s2][s3] = true;
                q.push({t.day + 1, x, y, s0, s1, s2, s3});

            }
    }

    return 0;
}


int main()
{
    //对数据循环 读取-> 处理 -> 输出
    while(cin >> n, n)
    {
        for(int i = 1; i <= n; i++)
            for(int j = 0; j < 4; j++)
                for(int k = 0; k < 4; k++)
                    cin >> state[i][j][k];

        cout << bfs() << endl;
    }

    return 0 ;
}




双端bfs,现学现卖, 交一个, C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

const int N = 6;

int n;
string A, B;
string a[N], b[N];


int extend(queue<string>& q,unordered_map<string, int>& da, unordered_map<string, int>& db, string a[N], string b[N] )
{
    //当前要被扩展的字符串是第几次扩展
    int d = da[q.front()] ; 

    //限制扩展的层数
    while(q.size() && da[q.front()] == d)
    {
        auto t = q.front();
        q.pop();
        for(int i = 0 ; i < n; i++)
            for(int j = 0; j < t.size(); j++)

                //找到可以替换的符合条件的子串
                if(t.substr(j, a[i].size()) == a[i])
                {
                    //进行替换
                    string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
                    //如果两端都寻找到
                    if(db.count(r)) return da[t] + db[r] + 1;
                    if(da.count(r)) continue;
                    da[r] = da[t] + 1;
                    q.push(r);
                }
    }

    return 11;
}



int bfs()
{
    queue<string> qa, qb;
    unordered_map<string, int> da, db;

    qa.push(A);
    qb.push(B);
    da[A] = 0;
    db[B] = 0;

    int step = 0;
    while(qa.size() && qb.size())
    {
        int t;
        //哪边的队列短就先扩展哪个数列
        if(qa.size() < qb.size()) t = extend(qa, da, db, a, b);
        else t = extend(qb, db, da, b, a);

        if(t <= 10) return t;
        //超过了10次就终止
        if(++step == 10) return -1;
    }
    return -1;
}


int main()
{
    cin >> A >> B;
    while(cin >> a[n] >> b[n]) n++;
    int t = bfs();
    if(t == -1) puts("NO ANSWER!");
    else cout << t << endl;

    return 0;
}



C++ 代码

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;
const int N = 110;

int n, m;
int dist[N][N];
char g[N][N];

typedef pair<int, int> PII;
PII start;

int bfs()
{
    int res = 0;
    memset(dist, -1, sizeof dist);
    queue<PII> q;
    q.push(start);
    dist[start.x][start.y] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int x = t.x - 1; x <= t.x + 1; x++)
            for(int y = t.y - 1; y <= t.y + 1; y++)
            {
                if(x < 1 || x > n || y < 1 || y > m || g[x][y] == '*' || dist[x][y] != -1) continue;
                dist[x][y] = dist[t.x][t.y] + 1;
                res = max(res, dist[x][y]);
                q.push({x, y});
            }

    }
    return res;
}


int main()
{
    cin >> m >> n >> start.y >> start.x;
    start.x = n - start.x + 1;

    for(int i = 1; i <= n; i++)
        cin >> g[i] + 1;

    cout << bfs() << endl;

    return 0;
}