图基础

基本概念

连通：如果图中结点U、V之间存在一条从U通过若干条边、点到达V的通路，则称U、V是连通的

完全图：每对顶点之间有唯一的一条边相连或想通。无向图共有：n*(n-1)/2条边，有向图共有：n*(n-1)条边

子图: 边的子集和相关联的点集

强联通分量：有向图中任意两点都连通的最大子图

补图：对于(u,v), 若邻接则改为非邻接, 若非邻接则改为邻接, 得到的图为原图的补图

团：完全子图

割点：如果从图中删去某点和与该点相关联的边后，图不再连通，那么这个点叫做割点，也称顶点或关节点

割边：如果从图中删去某条边后，图不再连通，那么这条边叫做割边或桥

割点与割边

若生成树的根有两棵或两棵以上的子树，则此根顶点必为割点。
若生成树中某个非叶子顶点v，它的子树中的任一结点均没有指向v的祖先的回边，则v为割点。

(ps:我们定义dfn[i]为节点i搜索的次序编号(时间戳)，low[i]为i或i的子树能够追溯到的最早的栈中节点的次序号。)

实现：当low[j]<dfn[i](j是i的儿子)时，说明j或者j的子孙中存在指向i祖先的回边。反之，若对于某个顶点v，存在孩子结点w，且low[w]>=dfn[v],表明w及其子孙均无指向v的祖先的回边，则该顶点v必为割点。

在任何DFS树中，当且仅当不存在回边连通w的子孙与w的祖先时，树边v-w是一座桥。

实现：与割点类似的，我们定义low[]和dfn[]。父子边e=u→v ，当且仅当low[v] > dfn[u]的时候，e是割边。

强连通分量Tarjan算法

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。dfs时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

当dfn(u)=low(u)时，以u为根的搜索子树上的所有节点构成一个强连通分量。

例题：洛谷2341受欢迎的牛

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 const int M=60000,N=20000;
  6 struct node
  7 {
  8     int to;         //这条边到达的点 
  9     int next;       //下一条边的编号 
 10 }a[M];              //链式前向星 
 11 int b[N];           //链式前向星 
 12 int n,m;            //n:奶牛数;m:喜欢关系数
 13 int bnum=0;         //边数 
 14 int dfn[N],low[N];  //dfn[i]:表示结点i是第dfn[i]个被访问到的结点
 15                     //low[i]用来记录i及i的子孙相连的辈分最高的祖先的访问时间戳
 16 int top,st[N];      //top:栈的指针;st:栈 
 17 int tot;            //遍历序数 
 18 bool f[N];          //是否考虑过 
 19 int cnum;           //标记不同的强连通分量 
 20 int be[N];          //被标记到不同强连通分量 
 21 int size[N];        //size[i] 被标记为i的强连通分量的个数 
 22 bool w[N];          //w[i]:被标记为i的强连通分量是否有出度 1:有;0:没有; 
 23 int read()          //读入优化 
 24 {
 25     int sum=0;
 26     char ch;
 27     ch=getchar();
 28     while(ch>'9'||ch<'0') ch=getchar();
 29     while(ch>='0'&&ch<='9') sum=sum*10+ch-'0',ch=getchar();
 30 //    cout<<"read: "<<sum<<endl;
 31     return sum;
 32 }
 33 void lian(int to,int from)    //链式前向星   to,from!!!!!!! 
 34 {
 35     a[++bnum].next=b[from];  //cout<<from<<" "<<to<<"  !"<<endl;
 36     a[bnum].to=to;
 37     b[from]=bnum;
 38 }
 39 void dfs(int x)
 40 {
 41     dfn[x]=low[x]=++tot;             //初始 dfn low 值 
 42     st[++top]=x;                     //入栈 
 43     f[x]=1;                         
 44     for(int i=b[x];i;i=a[i].next)
 45     {
 46         if(!dfn[a[i].to])
 47         {
 48             dfs(a[i].to);
 49             low[x]=min(low[x],low[a[i].to]);     //更新 low 值 
 50         }
 51         else if(f[a[i].to])          //如果走过   是回边 
 52         {
 53             low[x]=min(low[x],low[a[i].to]);
 54         }
 55     }
 56     if(low[x]==dfn[x])
 57     {
 58         cnum++;         //标记强连通分量 
 59         int now;      
 60         while(now!=x)
 61         {
 62             now=st[top--];
 63             be[now]=cnum;
 64             size[cnum]++; 
 65         } 
 66         /*for(int i=top+1;i<=top+size[cnum];i++)         //是否有出度 
 67         {
 68             if(!w[cnum]) 
 69             for(int j=b[i];j;j=a[j].next)
 70             {
 71                 if(be[a[j].to]!=cnum) 
 72                 {w[cnum]=1;break;}           //有出度 不是强连通分量 
 73             }
 74         }*/
 75     }
 76 }
 77 int main()
 78 {
 79     n=read();m=read();             //read:读入优化 
 80     for(int i=1;i<=m;i++)
 81     {
 82         lian(read(),read());
 83     }
 84     for(int i=1;i<=n;i++)        //dfs：寻找强连通分量 
 85     {
 86         if(!dfn[i]) dfs(i);
 87     }
 88     for(int i=1;i<=n;i++)
 89     {
 90         if(w[be[i]]) continue;
 91         for(int j=b[i];j;j=a[j].next)
 92         {
 93             if(be[i]!=be[a[j].to])
 94             {
 95                 w[be[i]]=1;
 96                 break;
 97             }
 98         }
 99     } 
100     int ans=0;   //最终答案 
101     for(int i=1;i<=cnum;i++)
102     {
103         if(!w[i])
104         {
105             if(ans)
106             {
107                 putchar('0');
108                 return 0;
109             }
110         else ans=size[i];
111         }
112     }
113     printf("%d",ans);
114     return 0;
115 }

View Code

最短路问题

Dijkstra：单源最短路，不含负权
bellman-ford：单源最短路，可含负权，但不能有负权回路：
SPFA：Bellman-ford的队列优化
floyd-warshall：每两对点的最短路，可含负权

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 using namespace std;
 5 int ans[10010];
 6 bool f[10010];
 7 struct node
 8 {
 9     int to;
10     int data;
11     int next;
12 }a[1000010];
13 struct cmp
14 {
15     bool operator()(int a,int b)
16     {
17         return ans[a]<ans[b];
18     }
19 };
20 int b[10010];
21 int tot;
22 priority_queue<int,vector<int>,cmp>h;
23 void lian(int from,int to,int sum)
24 {
25     a[++tot].next=b[from];
26     a[tot].to=to;
27     a[tot].data=sum;
28     b[from]=tot;
29 }
30 int main()
31 {
32     int n,m,s;
33     cin>>n>>m>>s;
34     for(int i=1;i<=n;i++) ans[i]=2147483647;
35     for(int i=1;i<=m;i++)
36     {
37         int a,b,c;
38         cin>>a>>b>>c;
39         lian(a,b,c);
40     }
41     ans[s]=0;
42     h.push(s);
43     f[s]=1;
44     int num=0;
45     for(int k=1;k<=n;k++)
46     {
47         int num;
48         num=h.top();
49         f[num]=0;
50         h.pop();
51         if(num)
52         {
53             f[num]=1;
54             for(int i=b[num];i;i=a[i].next)
55             {
56                 ans[a[i].to]=min(ans[a[i].to],ans[num]+a[i].data);
57                 h.push(a[i].to); 
58             }
59         }
60     }
61     for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
62     return 0;
63 }

Dijkstra+堆优化

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int M=21000;
 5 struct node
 6 {
 7     int to;
 8     int data;
 9     int next;
10     int from;
11 }a[1000010];
12 int b[1010];
13 int ans[1010];
14 int tot=0;
15 void lian(int from,int to,int sum)
16 {
17     a[++tot].next=b[from];
18     a[tot].to=to;
19     a[tot].data=sum;
20     a[tot].from=from;
21     b[from]=tot;
22  } 
23 int main()
24 {
25     int n,m;
26     cin>>n>>m;
27     for(int i=1;i<=n;i++) ans[i]=M;
28     for(int i=1;i<=m;i++)
29     {
30         int a,b,c;
31         cin>>a>>b>>c;
32         lian(a,b,c);
33         if(a==1) ans[b]=c;
34     }
35     for(int k=1;k<=n-1;k++)
36     {
37         for(int i=1;i<=m;i++)
38         {
39             if(ans[a[i].from]*a[i].data<ans[a[i].to])
40             {
41                 ans[a[i].to]=ans[a[i].from]*a[i].data;
42             }
43         }
44     }
45     cout<<ans[n];
46     return 0;
47 }

Bellman Ford

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 const int M=21000000;
 6 struct node
 7 {
 8     int to;
 9     int data;
10     int next;
11     int from;
12 }a[1000010];
13 int b[1010];
14 int ans[10010];
15 bool f[10010];
16 int tot=0;
17 queue<int>h;
18 void lian(int from,int to,int sum)
19 {
20     a[++tot].next=b[from];
21     a[tot].to=to;
22     a[tot].data=sum;
23     a[tot].from=from;
24     b[from]=tot;
25  } 
26 int main()
27 {
28     int n,m,s;
29     cin>>n>>m>>s;
30     for(int i=1;i<=n;i++) ans[i]=M;
31     for(int i=1;i<=m;i++)
32     {
33         int a,b,c;
34         cin>>a>>b>>c;
35         lian(a,b,c);
36     }
37     h.push(s);f[s]=1;
38     ans[s]=0;
39     while(!h.empty())
40     {
41         int q=h.front();h.pop();
42         f[q]=0;
43         for(int i=b[q];i;i=a[i].next)
44         {
45             if(ans[q]+a[i].data<ans[a[i].to])
46             {
47                 if(!f[a[i].to])  
48                 {
49                     h.push(a[i].to);
50                     f[a[i].to]=1;
51                 }
52                 ans[a[i].to]=ans[a[i].from]+a[i].data;
53                }
54         }
55     }
56     for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
57     return 0;
58 }

SPFA

最小生成树

Prim算法（加点法）
Kruskal算法（加边法）

 1 //https://www.luogu.org/problemnew/show/P3366 
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 int n,m;
 6 int data[5010][5010];    //data[i][j]:i到j的路长度
 7 int dis[5100]; 
 8 bool f[5100];         //是否为生成树中的点 
 9 int read()           
10 {
11     int sum=0;
12     char ch;
13     ch=getchar();
14     while(ch>'9'||ch<'0') ch=getchar();
15     while(ch>='0'&&ch<='9') sum=sum*10+ch-'0',ch=getchar();
16     return sum;
17 }
18 int main()
19 {
20     n=read();m=read();
21     for(int i=1;i<=n;i++) dis[i]=210000;
22     for(int i=1;i<=m;i++)
23     {
24         int a,b,c;
25         a=read();b=read();c=read();
26         if(c<data[a][b]||!data[a][b]) data[a][b]=data[b][a]=c;
27         //if(a==1) dis[b]=c;
28     }
29     dis[1]=0;
30     int ans=0; 
31     for(int k=1;k<=n;k++)
32     {
33         int num1=210000,num2=0;
34         for(int i=1;i<=n;i++)
35         {
36             if(dis[i]<num1&&!f[i])
37             {
38                 num1=dis[i];
39                 num2=i;
40             }
41         }
42         if(num2)
43         {
44             ans+=dis[num2];
45             f[num2]=1;
46             for(int i=1;i<=n;i++)
47             {
48                 if(data[num2][i]!=0&&data[num2][i]<dis[i]&&!f[i])
49                 {
50                     dis[i]=data[num2][i];
51                   }
52             }
53         }
54     }
55     for(int i=1;i<=n;i++)
56     if(!f[i]) {cout<<"orz";return 0;}
57     cout<<ans;
58     return 0; 
59 }

最小生成树 Prim

1 //太简单了我不写了qwq

最小生成树Kruskal

差分约束系统

只想补充讲一点啦（第一张图片中的图中）：0-3的每一条路的权值其实都是由经过路径所代表的不等式综合起来的最大值由于要满足每个不等式，所以求这些最大值的最小值

例题：[SCOI2011]糖果

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 inline int read()
 6 {
 7     char ch;int sum=0;
 8     ch=getchar();
 9     while(ch<'0'||ch>'9') ch=getchar();
10     while(ch>='0'&&ch<='9') {sum=sum*10+ch-'0';ch=getchar();};
11     return sum;
12 }
13 int n,m;
14 int a[100010],num;
15 struct node
16 {
17     int to,data,next;
18 }b[200010];
19 void lian(int from,int to,int sum)
20 {
21     b[++num].next=a[from];
22     b[num].to=to;
23     b[num].data=sum;
24     a[from]=num;
25 }
26 queue<int> h;
27 int dis[100010];
28 bool f[100010];         //是否在队列中 
29 int nn[100010];
30 bool SPFA()
31 {
32     dis[0]=0;        
33     f[0]=1;
34     h.push(0); 
35     while(!h.empty())
36     {
37         int x=h.front();
38         h.pop();
39         f[x]=0;
40         for(int i=a[x];i;i=b[i].next)
41         {
42             //cout<<"!";
43             if(b[i].data+dis[x]>dis[b[i].to])
44             {
45                 dis[b[i].to]=b[i].data+dis[x];
46                 if(!f[b[i].to]) 
47                 {
48                     if(++nn[b[i].to]>n) {cout<<b[i].to<<endl;return 0;}
49                     h.push(b[i].to);
50                     f[b[i].to]=1; 
51                 }
52             }
53         }
54     }
55     return 1;
56 }
57 int main()
58 {
59     n=read();m=read();
60     for(int i=1;i<=m;i++) 
61     {
62         int x,a,b;
63         x=read();a=read();b=read();
64         if(x==1) 
65         {
66             lian(a,b,0);
67             lian(b,a,0);
68         }
69         if(x==2)
70         {
71             if(a==b) {cout<<"-1";return 0;}
72             lian(a,b,1);
73         }
74         if(x==3) lian(b,a,0);
75         if(x==4)
76         {
77             if(a==b) {cout<<"-1";return 0;}
78             lian(b,a,1);
79         }
80         if(x==5) lian(a,b,0);
81     }
82     for(int i=1;i<=n;i++)
83     lian(0,i,1);                    ////每个小朋友都至少有一个糖果!!!!
84     if(!SPFA()) {cout<<"-1";return 0;};
85 long long ans=0;
86     for(int i=1;i<=n;i++) ans+=dis[i];
87     cout<<ans;
88     return 0;
89 }

差分约束系统+SPFA

LCA

在这里qwq

负环

 1 // luogu-judger-enable-o2
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<cstring>
 6 using namespace std;
 7 int read()
 8 {
 9     int ans=0,x=1;char c;
10     c=getchar();
11     while(c<'0'||c>'9') {if(c=='-') x=-1;c=getchar();}
12     while(c>='0'&&c<='9') {ans=ans*10+c-'0';c=getchar();}
13     return ans*x;
14 }
15 const int N=100010;
16 
17 struct node         //链式前向星 
18 {
19     int to,data,next;
20 }a[N]; 
21 int b[N],num;
22 void lian(int u,int v,int w)
23 {
24     a[++num].next=b[u];
25     a[num].to=v;
26     a[num].data=w;
27     b[u]=num;
28 }
29 
30 int n,m;
31 bool vis[N];
32 int dis[N],times[N];
33 
34 bool spfa()
35 {
36     for(int i=1;i<=n;i++) {vis[i]=0;dis[i]=2100000000;times[i]=0;}
37     queue<int>h;
38     h.push(1);
39     vis[1]=1;
40     dis[1]=0;
41     while(!h.empty())
42     {
43         int u=h.front();h.pop();vis[u]=0;
44         //cout<<u<<"  !"<<endl;
45         if(times[u]>=n) return 1;
46         for(int i=b[u];i;i=a[i].next)
47         {
48             int v=a[i].to;
49             if(dis[v]>dis[u]+a[i].data)
50             {
51                 dis[v]=dis[u]+a[i].data;
52                 if(!vis[v])
53                 {
54                     h.push(v);
55                     vis[v]=1;
56                     times[v]++;
57                     if(times[v]>=n) return 1;
58                 }
59             }
60         }
61     }
62     return 0;
63 }
64 int main()
65 {
66     int t=read();
67     while(t--) 
68     {
69         n=read(),m=read();
70         num=0;
71         memset(b,0,sizeof(b));
72         for(int i=1;i<=m;i++)
73         {
74             int x=read(),y=read(),z=read();
75             lian(x,y,z);
76             if(z>=0) lian(y,x,z);
77         }
78         puts(spfa()?"YE5":"N0");
79     }
80     return 0;
81 }

SPFA

光伴随的阴影

图 基础

图基础