[关闭]
@Superjohnson 2017-10-04T12:30:14.000000Z 字数 8015 阅读 1546

NOIp要考的图论

主讲：张浩威 alpq尾号4321

图论 清北 笔记

图论：算法简单，但是难点在于构图。

noip要考的图论算法

图的定义

一个图由点的集合与边的集合构成。
一条连接u,v的边用(u,v)表示，当u=v时存在自环。
在有向图中所有边都是有向的，也就是说(u,v)≠(v,u)。
在无向图中所有边都是无向的，也就是说(u,v)=(v,u)。
定义一个点v的入度为(u,v)中u的个数。
定义一个点u的出度为(u,v)中v的个数。
每条边可能存在权值。
定义w1,w2,…,wp为图的一条路径当且仅当存在(w1,w2),(w2,w3),…,(w{p-1},wp)。
一条路径称为简单路径，当且仅当w互不相同。
当图是无向时，路径的长度为边的条数，否则为边权之和。
若一条路径w1=wp，则我们称这条路径为这个图的一个环。
对于无向图，若任意两点之间是可达的，我们称这张图是连通的。
对于有向图，若任意两点之间互相可达，我们称这张图为强连通。否则若将其变成无向图后这张图是连通的，我们称这张图为弱连通。
我们称A是B的子图，当且仅当B的点集包含A的点集，且B的边集包含A的边集。
若此时A是强连通的，且不存在一个图C，使得A是C的子图且C强连通，则称A是B的极大强连通分量。
不可能有一个点存在于两个极大强连通分量。
一个图中若任意两个不同的点u,v都存在(u,v)与(v,u)，则称这个图为完全图。

竞赛图：有向图 任意两个点中有且只有一条边。

图的表示方式

临界矩阵存储

优点：方便，快捷！
缺点：需要n^2的空间，容易MLE
需要n^2的空间，访问一个点的所有边时时间复杂度为O(n)。
适用于完全图或者稠密图中。

邻接表存储

当图比较稀疏时，一般用邻接表，空间复杂度为O(|V|+|E|)！

链式前向星

  1. cin>>u>>v;
  2. o++;
  3. e[o]=v; // (u->v) 之前 u还指向过一些点  head[u]来表示起点为u的边编号最大的那个编号是多少
  4. next[o]=head[u];//当u处理完连向v的这条边之后，下一次处理的边编号是多少。
  5. head[u]=o;//           更新head[u]

遍历u为起点，能连向哪些点。

  1. for (i=head[u]; i!=0; i=next[i]) (u -> e[i]);

以下都是图论算法喽

拓扑排序

如果存在一个排列a1,a2,…,an，使得在该图中不存在ai到aj的路径(i>j)，我们称这个排列为这个图的拓扑序列。
我们每次寻找入度为0的点加入序列中。
并将当前点连接的所有边均删除，更新其它点的度数。
由于每条边至多被删除一次。
因此这个时间复杂度是O(|E|)的。

博客1 博客2

最短路

Dijkstra算法

令dis[i]表示当前u到i的最短路是多少。
①将dis[u]=0,dis[i]=inf(i!=u)。
②寻找最小的dis[x]且x曾经没被找到过。
③若x=v，输出答案并退出。
④枚举x的所有边，用dis[x]去更新其余dis[]，回到步骤②。
时间复杂度为n^2。
使用范围：不存在负权边。

SPFA

令dis[i]表示当前u到i的最短路是多少。
①将dis[u]=0,dis[i]=inf(i!=u)，并将u加入队列中。
②设当前队首为x，枚举x。
③枚举x的所有边，用dis[x]去更新其余dis[]，若dis[i]此时被更新且i当前不在队列中，将其加入队列。
④将x弹出队列，若此时队列为空，结束，否则返回步骤②。
邻接表版的：

  2. void SPFA(){
  3.     for(int i=1; i<=gv; i++)
  4.         Dist[i] = 100000;
  5.     Dist[S] = 0;
  6.     int closed = 0, open = 1;
  7.     queue[1] = S;
  8.     Inqueue[S] = true;
  9.     do{
  10.         closed++;
  11.         node *tmp = connect[queue[closed]];
  12.         Inqueue[queue[closed]] = false;
  13.         while(tmp != NULL){
  14.             if( Dist[tmp->key] > Dist[queue[closed]] + tmp->w ){
  15.                 Dist[tmp->key] = Dist[queue[closed]] + tmp->w;
  16.                 Path[tmp->key] = queue[closed];
  17.                 if( !Inqueue[tmp->key] ){
  18.                     Inqueue[tmp->key] = true;
  19.                     open++;
  20.                     queue[open] = tmp->key;
  21.                 }
  22.             }
  23.             tmp = tmp->next;
  24.         }
  25.     }while(closed < open);
  26. }

然后是邻接矩阵的：

  1. void SPFA(){
  2.     for( int i=1; i<=gv; i++){
  3.         Dist[i] = 100000;
  4.         for( int j=1; j<=gv; j++)
  5.             if( !Graph[i][j] && i!=j) Graph[i][j] = 100000;
  6.     }
  7.     int closed = 0, open = 1;
  8.     queue[1] = S;
  9.     Dist[S] = 0;
  10.     do{
  11.         closed++;
  12.         int u = queue[closed];
  13.         Inqueue[u] = false;
  14.         for(int i=1; i<=gv; i++)
  15.             if ( Dist[i] > Dist[u] + Graph[u][i] ){
  16.                 Dist[i] = Dist[u] + Graph[u][i];
  17.                 Path[i] = u;
  18.                 if( !Inqueue[i] ){
  19.                     Inqueue[i] = true;
  20.                     open++;
  21.                     queue[open] = i;
  22.                 }
  23.             }
  24.     }while(closed < open);
  25. }

并查集

啥是并查集？
我朋友的朋友就是我的朋友！
常用于判断两点是否连通。
一行并查集（作者对这种做法嗤之以鼻）

  1. int getf(int k) {return f[k]==k?f[k]:f[k]=getf(f[k]);}

用了路径压缩优化。
时间复杂度为nα(n)，其中α是个反阿克曼函数，增长速度极慢。

e.g. 校门外的树（我也很疑惑为什么要讲这道题）

最小生成树（MST）

Kruskal

主要思想：对边权进行排序，判断能否形成环，如果不形成，就加入。

Prim

主要思想：一开始随便找一个点做集合中点，每次找一条最短边，要求一个点在集合，一个不在，加入集合。

引申：次小生成树，严格次小生成树，生成树计数，最优比率生成树（放心，NOIp不考）

二分图

如果一个无向图G中V能分成两个点集A与B，且位于A中的顶点互相之间没有边，位于B中的顶点互相之间没有边，则称这个图为二分图。


v是点集，e是边集
所有边连接的两个点分别为两个集合的点的图即为二分图。

如何判断一个图是不是二分图？

判断方法1：判断点颜色（属于的集合）
col数组，代表不同颜色。
代码实现：

  1. vector <int> v[N];
  2. void dfs(int x,int y)
  3. {
  4.   col[x]=y;
  5.   for (int i=0; i<v[x].size(); i++)
  6.   {
  7.      if (!col[v[x][i]]) dfs(v[x][i],3-y);
  8.      if (col[v[x][i]]==col[x]) FLAG=true;
  9.   }
  10. }
  11. for (i=1; i<=n; i++) col[i]=0;
  12. for (i=1; i<=n; i++) if (!col[i]) dfs(i,1);
  13. if (FLAG) cout<<"NO"; else cout<<"YES";

判断方法2：判断边所连接的点属不属于两个集合。
类似于并查集的方法。

注意：并查集是一种算法，而二分图是一种概念，一种数据结构

代码实现：

  1. int getf(int k) {return f[k]==k?f[k]:f[k]=getf(f[k]);}
  2. for (i=1; i<=n; i++) p[i][0]=++cnt,p[i][1]=++cnt;
  3. for (i=1; i<=cnt; i++) f[i]=i;
  4. for (i=1; i<=m; i++)
  5. {
  6.   u-v
  7.   f[getf(p[u][0])]=getf(p[v][1]);
  8.   f[getf(p[u][1])]=getf(p[v][0]);
  9.   if (getf(p[u][0])==getf(p[u][1]) || getf(p[v][0])==getf(p[v][1])) FLAG=true;
  10. }
  11. if (FLAG) puts("NO"); else puts("YES");

e.g. NOIp2010 提高组 关押罪犯

二分图匹配问题 （匈牙利算法）

顾名思义，在一个二分图中选择最多的边，使得没有任何一个点有连接它的两条边被选择到。
更加人性化的配对和相亲

  1. bool dfs(int x)
  2. {
  3.   for (int i=0; i<v[x].size(); i++)
  4.   if (!V[v[x][i]])
  5.   {
  6.     r++; st[r]=v[x][i];
  7.     V[v[x][i]]=true;
  8.     if (!p[v[x][i]])
  9.     {
  10.       p[v[x][i]]=x;
  11.       return true;
  12.     } else 
  13.       if (dfs(p[v[x][i]]))
  14.       {
  15.          p[v[x][i]]=x;
  16.          return true;
  17.       }
  18.   }
  19.   return false;
  20. }
  21. for (i=1; i<=|A|; i++)
  22. {
  23.   for (int j=1; j<=r; j++) V[st[j]]=false; r=0;
  24.   if (dfs(i)) ans++;
  25. }

e.g.
有n个奇数，把它写成二进制，只保留其中一个“1”，要使得异或和最大（n<=100,ai∈（0,2^31））

Sample Input:
3
5 3 5

Sample Output:
7

样例解释

标题 a[1] a[2] a[3]
十进制 5 3 5
转换为二进制 101 11 101
剩余一个“1”后 001 10 100

=> 111(2)
=> 7(10)

最大权匹配 最大流 费用流

有人说：匈牙利不如直接用最大流
自己看着办喽

搜索树

对一个图从某一点开始进行深度优先搜索。搜索到的边构成的树称为搜索树。在这棵树上的边称为树边，其余边称为非树边。
性质：对图求搜索树时，非树边连接的两个端点在搜索树中一定是其中一个点是另一个点的祖先。

强联通分量

任意两个点互相可达
无向图的所有点都是强联通分量；-）
那求有向图累？
Tarjan！

Tarjan(NOIp也不考)

明确两个名词：DFN LOW
DFN[x]：时间戳（第几次被DFS到）
LOW[x]：搜索树中x以及它的子孙可以访问到的最早祖先（x及x的所有子孙能访问到的最小时间戳）
博客1 博客2
zhw一开始也是背的，尽量去理解吧。
代码实现：

  1. //mx大佬的模板
  2. void tarjan(int u){
  3.     dfn[u]=low[u]=++sum;
  4.     s.push(u);
  5.     visit[u]=true;
  6.     for(int i=head[u];~i;i=edg[i].nxt){
  7.         if(!dfn[edg[i].to]){
  8.             tarjan(edg[i].to);
  9.             low[u]=min(low[u],low[edg[i].to]);
  10.         }
  11.         else if(visit[edg[i].to])low[u]=min(low[u],dfn[edg[i].to]);
  12.     }
  13.     if(low[u]==dfn[u]){
  14.         int j;
  15.         sumscc++;
  16.         do{
  17.             j=s.top();
  18.             s.pop();
  19.             visit[j]=false;
  20.             scc[sumscc]++;
  21.             belong[j]=sumscc;
  22.         }while(j!=u);
  23.     }
  24. }

e.g. [HAOI2006]受欢迎的牛
缩点之后，如果有两个点出度为零，说明他们互相不认为对方受欢迎，答案就是0，如果只有一个点，那么这个点一定被所有牛都喜欢。答案就是数量

无向图的割点和割边

我们称一个点u为这个图的割点，当且仅当删去这个点以及与该点连接的所有边后，这个图不连通。
我们称一条边(u,v)为这个图的割边，当且仅当删去这条边后这个图不连通。

2-sat

判断是否矛盾
也没啥好写的

练习题目

T1. [HNOI2012]矿场搭建

给定一个n个点，m条边的无向图。要在这n个点选择若干点建造避难所，使得无论哪个点爆炸，每个点上的人（除了爆炸的那个点）都能逃到这个避难所去。
求最少避难所个数，以及在这个前提下的方案总数。

Format

Input

输入文件有若干组数据，每组数据的第一行是一个正整数 N（N<=500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

Output

输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。

Sample

Input

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

Output

Case 1: 2 4
Case 2: 4 1

Explainnation

Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；
Case 2 的一组解为(4,5,6,7)。

Solution

主要的方法都写在注释里面了。
用Tarjan跑出割点，然后DFS搜索所有的联通快
计算每一个联通快中的割点数目
分类讨论：
如果没有割点
至少需要建立两个出口
从任意非割点的地方选择两个点建立
如果这个分组只有一个割点
只需要在分组内设立一个出口
可以设立在任意一个非割点的地方
如果有两个及以上个割点，则无需建立，可以直接到达其他联通块

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<cmath>
  6. #include<algorithm>
  7. using namespace std;
  9. #define MAX 501
  11. int Dfn[MAX],vis[MAX],Low[MAX];
  12. bool cut[MAX];
  13. long long Num,Cut,Time,root,rs,m,n,Ans1,Ans2,Case,Group;
  15. void Init();//多组数据，初始化 
  17. struct Node  //定义边 
  18. {
  19.        int v,next;
  20. }e[MAX*MAX];
  22. int h[MAX],cnt;
  24. void Add(int u,int v)  //添加边 
  25. {
  26.       e[cnt]=(Node){v,h[u]};
  27.       h[u]=cnt++;
  28. }
  30. void Tarjan(int u,int f)  //Tarjan跑出所有割点 
  31. {
  32.        int v;
  33.        Dfn[u]=Low[u]=++Time;   
  35.        for(int i=h[u];i!=-1;i=e[i].next)//枚举所有直接连接的点 
  36.        {
  37.                 v=e[i].v;
  38.                 if(!Dfn[v])  //如果没有访问过，证明v是u的子节点 
  39.                 {
  40.                        Tarjan(v,u);
  41.                        Low[u]=min(Low[u],Low[v]); //更新Low值 
  42.                        if(Low[v]>=Dfn[u])  //如果v能够回到u或者u的祖先 
  43.                        {
  44.                                if(u!=root)    //如果u不是子树的根节点 
  45.                                    cut[u]=true; //u是割点 
  46.                                else 
  47.                                    rs++;      //根节点子节点数增加 
  48.                        }
  49.                 }
  50.                 else
  51.                    if(v!=f)    //如果v不是u的父节点，但是v已经访问过 
  52.                       Low[u]=min(Low[u],Dfn[v]);  //判断是否能够更新Low 
  53.        }
  54. }
  56. void DFS(int u)//DFS搜索一边联通块 
  57. {
  58.         int v;
  60.         vis[u]=Group; //标记组 
  61.         Num++;        //非割点数 
  63.         for(int i=h[u];i!=-1;i=e[i].next)//访问子节点 
  64.         {
  65.                v=e[i].v;
  66.                if(cut[v]&&vis[v]!=Group) //如果v是割点并且v没有在这个分组内被访问过 
  67.                {
  68.                         Cut++;         //割点数增加 
  69.                         vis[v]=Group;  //标记分组 
  70.                }
  71.                if(!vis[v])     //如果vis未被访问过 
  72.                    DFS(v);     //搜索v 
  73.         }
  74. }
  76. int main()
  77. {
  78.        long long u,v;       
  79.        Case=1;
  81.        while(cin>>m&&m)
  82.        {
  83.               Init(); //初始化 
  85.            for(int i=1;i<=m;++i)//读入边 
  86.            {
  87.                    cin>>u>>v;
  88.                    Add(u,v);
  89.                    Add(v,u);
  90.                    n=max(n,v);
  91.                    n=max(n,u);
  92.            }
  94.            for(int i=1;i<=n;++i)//Tarjan算法求割点 
  95.            {
  96.                      if(!Dfn[i])
  97.                      {
  98.                               root=i;
  99.                               rs=0;
  100.                               Tarjan(i,i);
  101.                               if(rs>=2)       //如果子树根节点的儿子数不少于2个，则这个根节点才是割点 
  102.                                   cut[i]=true;
  103.                      }
  104.            }
  106.            for(int i=1;i<=n;++i)//枚举所有点来搜索分组 
  107.            {
  108.                     if(!vis[i]&&!cut[i])//如果i节点没有被访问过并且不是割点 
  109.                     {
  110.                             ++Group;  //增加一个分组 
  111.                             Num=Cut=0;
  112.                             DFS(i);   //搜索这个分组 
  114.                             if(Cut==0)//如果没有割点 
  115.                             {
  116.                                       Ans1+=2;//至少需要建立两个出口 
  117.                                       Ans2*=(Num-1)*Num/2;//从任意非割点的地方选择两个点建立 
  118.                             }
  120.                             if(Cut==1)//如果这个分组只有一个割点 
  121.                             {
  122.                                 Ans1+=1;  //只需要在分组内设立一个出口 
  123.                                 Ans2*=Num;//可以设立在任意一个非割点的地方 
  124.                             }
  126.                             if(Cut>=2)//如果有两个及以上个割点，则无需建立，可以直接到达其他联通块 
  127.                             {
  128.                                 ; 
  129.                         } 
  130.                     }
  131.            }
  133.            cout<<"Case "<<Case++<<": "<<Ans1<<" "<<Ans2<<endl;//输出结果     
  134.        }
  136.        return 0; 
  137. }
  139. void Init()
  140. {
  141.        memset(h,-1,sizeof(h));
  142.        memset(Dfn,0,sizeof(Dfn));
  143.        memset(Low,0,sizeof(Low));
  144.        memset(cut,0,sizeof(cut));
  145.        memset(vis,0,sizeof(vis));
  146.        Time=cnt=n=Ans1=Group=0;
  147.        Ans2=1;
  148. }

T2. reward

老板给员工发工资，工资由初始工资与奖金组成。初始工资为888元，奖金为任意非负整数。
有些员工比较奇怪，认为自己的工资需要比别人的工资高，老板要在满足每个人的前提下分出的钱最少。
保证有解。
求至少多少钱。
n,m<=50000。

T3. lift

一幢大楼有n层，有个电梯，第i层的电梯能让人上升k[i]或者下降k[i]，但不能超过n或者低于1。
求至少按几次电梯，才能从a走到b。

T4. NOIp2013 货车运输

A国有n座城市，编号从1到n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

Format

Input

输入文件名为 truck.in。
输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道
路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

Output

输出文件名为 truck.out。
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货
车不能到达目的地，输出-1。

Sample

Input

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

Output

3
-1
3

Explainnation

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；
对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。

T5. 图的最短路

我们定义一张图的最短路为任意两点的最短路之和。
给定一个无权无向图，求每条边被删除时的图的最短路。
n<=100,m<=3000。

Solution

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注