图的基本存储的基本方式四

旧城等待， 2022-07-12 09:40 135阅读 0赞

图的基本存储的基本方式四  
Time Limit: 2500MS Memory Limit: 10000KB  
Submit Statistic  
Problem Description

解决图论问题，首先就要思考用什么样的方式存储图。但是小鑫却怎么也弄不明白如何存图才能有利于解决问题。你能帮他解决这个问题么？  
Input

多组输入，到文件结尾。  
每一组第一行有一个数n表示n个点。接下来给出一个n\*n的矩阵 表示一个由邻接矩阵方式存的图。  
矩阵a中的元素aij如果为0表示i不可直接到j，1表示可直接到达。  
之后有一个正整数q，表示询问次数。  
接下来q行每行有一个询问，输入两个数为a，b。  
注意：点的编号为0~n-1，2<=n<=5000，0<=q<=100,0 <= a,b < n。  
保证可达边的数量不超过1000  
Output

对于每一条询问，输出一行。若a到b可以直接连通输出Yes，否则输出No。  
Example Input

2  
0 1  
0 0  
2  
0 1  
1 0  
Example Output

Yes  
No

其实说起来这题也并不难，不过我却没有完全是靠自己做出来，真是惭愧

此题的思想在于讲图的起始，终止，权存入到一个结构体内，之后用一个快排按题目要求的排序好就行了，其实很简单呐！

#include <stdio.h>
    #include <stdlib.h>
    
    struct node
    {
        int a;
        int b;
        int c;
    } head[500000];
    
    void quick_sort(int l,int r)
    {
        int i,j,k;
        i = l, j = r;
        if(l>=r)
            return;
        struct node key;
        key = head[l];
        while(i<j)
        {//快排这里要注意或者条件要极其注意加括号啊
            while(i<j&&(key.c<head[j].c||(key.c==head[j].c&&key.a<head[j].a)||(key.c==head[j].c&&key.a==head[j].a&&key.b<head[j].b)))
            {     j--;      }
            head[i]=head[j];
            while(i<j&&(key.c>head[i].c||(key.c==head[i].c&&key.a>head[i].a)||(key.c==head[i].c&&key.a==head[i].a&&key.b>head[i].b)))
            {     i++;      }
            head[j] = head[i];
        }
        head[i] = key;
        quick_sort(l,i-1);
        quick_sort(i+1,r);
    }
    
    int main()
    {
        int i,j,k;
        int n,m,q;
        while(~scanf("%d %d",&n,&m)){
            for(i=0; i<m; i++)
                scanf("%d %d %d",&head[i].a,&head[i].b,&head[i].c);
            quick_sort(0,m-1);
            scanf("%d",&q);
            while(q--){
                scanf("%d",&j);
                printf("%d %d\n",head[j].a,head[j].b);
            }
        }
        return 0;
    }