图论之建立基础的图

十二月 31, 2017 1147

指针建图

学（背）会建立一个基础的图，是写好图论算法的基础。

具体就是写一个循环，通过构造函数来创建一个一个的边和结点
附代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define Inf 2e31-1
#define DEBUG(x) std::cerr << #x << '=' << x << endl;
#define MAXN 2500 + 5
//设定图的最大结点值为2500

struct Node;
struct Edge;
struct Node{
  Edge *firstEdge;
  int dist;
  bool inQueue;
} node[MAXN];

struct Edge{
  Node *s,*t;
  int w; //权值
  Edge *next; //下一条边

  Edge(Node *s,Node *t,int w) : s(s),t(t),w(w),next(s->firstEdge);
  //构造函数
};
inline void add(const int &s,const int &t,const int &w){
  node[s].firstEdge = new Edge(&node[s],&node[t],w);
  node[t].firstEdge = new Edge(&node[t],&node[s],w);
}
/*      code here
 *  请在这里写各种的函数
 */
 int main(int argc, char const *argv[]) {
   int n,m,s,t;
   ios::sync_with_stdio(false);
   cin >> n >> m >> s >> t;
   for (int i = 1;i <= m;i++){
     int u,v,w;
     cin >> u,v,w;
     add(u,v,w);
   }
   /* code here*/
   return 0;
 }