@LittleRewriter 2017-10-08T02:24:20.000000Z 字数 6124 阅读 983

图论

图论

友链https://www.zybuluo.com/Superjohnson/note/905505
ORZ!
算法简单，难点在于构图

算法

最短路
最小生成树
拓扑排序
二分图最大匹配
Tarjan
并查集
~~2-SAT~~
~~网络流~~

构图

比如，给定n个奇数，拆成二进制，只保留其中一位，求最大抑或和。
这种糟东西是最难的图论

图的定义

自环
有向与无向
带权边
路径
- 简单路径
连通分量
- 强联通分量
- 极大强联通分量　一个点不可能存在与两个极大强联通分量
子图
完全图
竞赛图　　任意两点间有一条有向边

图的表示

邻接矩阵很方便 f[i][j]>0表示存在边，但是很占空间 $O(N^2)$
map存边也很方便，但是很慢
邻接表

//数组实现
cin>>u>>v;
f[u][++f[u][0]]=i;
//f[u][0]为能连出来几个点，f[u][i]表示第i个点是啥
//复杂度是O(出度)
//向量实现
vector<int> f[n];
cin>>u>>v;
f[u].push_back(v);
//内存复杂度O(m)
//查询O(出度)

边表（前向星，链式前向星）

//预处理
cin>>u>>v;
o++
e[o]=v;//用head[u]表示起点为u最大的编号
next[o]=head[u];//u处理完连向v的这条边之后下一条是什么
head[u]=o;//更新
//遍历u为起点能连向哪些点
for(i=head[u];i;i=next[i]) u->e[i];

~~zhw:我觉得没啥要用的地方~~

其它概念

-最大团、最大独立点集
选择一个图中的若干点，若任意两个点之间均有一条边联通，则这些点组成的集合是一个团。
最大团即最多的点组成的团。
选择一个图中的若干点，若任意两个点之间都没有一条边联通，则这些点组成的集合是一个独立点集。
最大独立点集即最多的点组成的独立点集。
最大团=n-最大独立点集。
求一个最大团是NP 暴搜n=59是极限（需要一天）

例给定一个点数为3n的图，保证图中存在一个点数不小于2n的团。求一个点数为n的团。n<=1000。

每次找两个点，没有边，然后删掉
重复n次，剩下的一定是团，保证2个点最多只有1个点在团里

给定一张带点权和边权的图，点权和边权都是正整数。选择这个图的一个子图，要求这个子图连通，它的价值为点权之和除以边权之和。
问这个最大价值是多少。点数，边数<=100000。

直接搞和最大的两个。
因为对于一个树，可以剖开两半，
无标题.png
a为根节点，de为左右子树的边权，bc为左右子树点权

$v=max(\dfrac{a+b}{d},\dfrac{a+c}{e})$
这是由于

$\dfrac{a+b}{d}>\dfrac{a+b+c}{d+e}$ .这个的证明：
假设 (a+b)/d >= (b+c)/e -> ae+be>=bd+cd
证 (a+b)/d > (a+b+c)/(d+e) -> ae+bd+be>bd+cd
而一个图，也是显然的。
所以综上所述，两个点连起来一条边就是最好的办法。因此这个题其实是个贪心题。

正解

cin>>n>>m;
for (i=1; i<=n; i++) cin>>a[i];
for (i=1; i<=m; i++)
{
  cin>>u>>v>>z;
  ans=max(ans,(a[u]+a[v])/(z+0.0));
}
printf("%.2f\n",ans);

拓扑排序

每次找入度为0的点加入序列，删掉周围的边，O(|E|)

例计数拓扑排序方案总数

$10^5$ 暴搜
$10^{18}$ 没办法
如果图有阶段就可以乘法原理

例给定一张n个点m条边的拓扑图（保证1号点能走到n号点），求存在多少点，将其删去后1号点走不到n号点。n，m<=100000。

这个点为所求当且仅当能从1走到并且能走到n
如果是一个拓扑图，那么就有一个序列只有左边到右边的路径，也就是该图是无后效性，可以用dp[i]表示从1号点走到i号点的方案总数
$dp[i]=\sum dp[j]|\exists(i,j)$

如果某个点是所求的点，那么这个点一定不存在跨越该点的边，否则这个点就不是。因此这里可以用乘法原理，f[k]·g[k]=f[n]

最短路

Dijkstra

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

SPFA

令dis[i]表示当前u到i的最短路是多少。
①将dis[u]=0,dis[i]=inf(i!=u)，并将u加入队列中。（相当于一次松弛）
②设当前队首为x，枚举x。
③枚举x的所有边，用dis[x]去更新其余dis[]，若dis[i]此时被更新且i当前不在队列中，将其加入队列。
④将x弹出队列，若此时队列为空，结束，否则返回步骤②。
期望O(km)，最坏O(nm)，网格图会卡，但是很好用
也可以判断负环：一个点进入超过n次就是负环

斯坦那树

Floyd

例题

给定一本词典，这个词典共有n个单词。以及两个长度相同且在词典中的字符串A和B。每次可以将A中的一个字母变成另一个字母，要求变化后这个单词仍在词典中，要求最少操作次数，使得A能变成B。
例如DAMP->LAMP->LIMP->LIME->LIKE。

对于n个单词，若修改一步能到达连一条无向边
求最短路即可
注意无边权的最短路可以宽搜跑(复杂度宽搜<=SPFA)

并查集

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

学校门口有n个点(1~n)，要种一堆树。种m次，每次在li~ri种一棵树。每次种完树后求有多少点还没种上树。n,m<=10000000。

线段树裸题,1kw会爆
并查集实现：
用f[i]表示从i开始向右最近的还没有种过树的

for(i=getf(i);i<=r;i=getf(i+1)){
    ++ans;
    f[i]=getf(i+1);
}

复杂度近似线性

给一个n节点的树，一开始边权为0，每次将一条链上的边权->1，求每次操作边权之和

树剖，复杂度 $O(Qlog^2n)$
树上的并查集维护：
f[i]表示链i向上最近的没有被变成1的边

for(i=getf(i);i<=r;i=getf(i+1)){
    ++ans;
    f[i]=getf(fa[i]);
}

还需要LCA。

最小生成树

Kruskal：边权排序，不成环加入，并查集维护

int cmp(node i,node j) {return i.z<j.z;}
for (i=1; i<=m; i++) cin>>t[i].u>>t[i].v>>t[i].z;
sort(t+1,t+m+1,cmp);
for (i=1; i<=m; i++) 
    if (getf(t[i].u)!=getf(t[i].v)) 
        {f[getf(t[i].u)]=getf(t[i].v); 
        ans+=t[i].z;}
cout<<ans;

找一个最大边权最小的最小生成树->反着取

次小生成树
严格次小生成树
生成树计数
最优比率生成树

以上NOIP并不会考

打水一个村庄有n个点，(i,j)之间都可以花费a[i][j]的代价造一条路径(有a[i][j]=a[j][i])，村民们想在这n个点选择若干点挖水井，第i个点挖水井的代价为w[i]，构造一个方案使得代价最小的情况下村民们都有水喝。

一个点打通=虚拟点相连，也就是变成连通图，然后虚拟点连一条w的边，跑一遍最小生成树

二分图

如果一个无向图G中V能分成两个点集A与B，且位于A中的顶点互相之间没有边，位于B中的顶点互相之间没有边，则称这个图为二分图。
如果不存在奇环就是二分图。
从一个点出发，染色。

判断

DFS判断：一开始令颜色为0，用颜色1表示点i染成黑色，2表示染成白色,0表示未被染色。

vector <int> v[N];
void dfs(int x,int y)
{
  col[x]=y;
  for (int i=0; i<v[x].size(); i++)
  {
     if (!col[v[x][i]]) dfs(v[x][i],3-y);//没有被染过则染色成3-i
     if (col[v[x][i]]==col[x]) FLAG=true;//颜色相同，有奇环
  }
}
for (i=1; i<=n; i++) col[i]=0;
for (i=1; i<=n; i++) if (!col[i]) dfs(i,1);
if (FLAG) cout<<"NO"; else cout<<"YES";

并查集判断：将每个点A裂成两个点A与A’。若A与B之间存在边，则连一条A与B’的边，A’与B的边。若此时A与A’连通，或者B与B’连通，则该图不是二分图。（若连通则必然出现了奇环）利用并查集实现即可。

int getf(int k) {return f[k]==k?f[k]:f[k]=getf(f[k]);}
for (i=1; i<=n; i++) p[i][0]=++cnt,p[i][1]=++cnt;
for (i=1; i<=cnt; i++) f[i]=i;
for (i=1; i<=m; i++)
{
  u-v
  f[getf(p[u][0])]=getf(p[v][1]);
  f[getf(p[u][1])]=getf(p[v][0]);
  if (getf(p[u][0])==getf(p[u][1]) || getf(p[v][0])==getf(p[v][1])) FLAG=true;
}
if (FLAG) puts("NO"); else puts("YES");

关押罪犯二分答案判断是否是二分图或者一次从小到大加边，并依次判断能否构成二分图。

最大匹配匈牙利（白学）算法

~~我tm只知道贵圈真乱~~

~~这里完全没有听懂...~~

bool dfs(int x)
{
  for (int i=0; i<v[x].size(); i++)
  if (!V[v[x][i]])
  {
    r++; st[r]=v[x][i];
    V[v[x][i]]=true;
    if (!p[v[x][i]])
    {
      p[v[x][i]]=x;
      return true;
    } else 
      if (dfs(p[v[x][i]]))
      {
         p[v[x][i]]=x;
         return true;
      }
  }
  return false;
}
for (i=1; i<=|A|; i++)
{
  for (int j=1; j<=r; j++) V[st[j]]=false; r=0;
  if (dfs(i)) ans++;
}
cout<<ans<<endl;

复杂度O(nm)
再来看下午的题。

给定n个奇数，拆成二进制，只保留其中一位，求最大抑或和。

这个东西完全没有听懂...所以直接放hzk神犇的了：
QQ截图20171004195915.png

搜索树

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

强联通分量

无向图

就是连通块

有向图的Tarjan算法

定义一个DFN为时间戳，即第几次被DFS到的
LOW[i]表示i与i的所有子孙能访问到的最小时间戳

void dfs(int x){
    DFN[x]=++Time;
    LOW[x]=DFN[x];//能访问到自己
    st[++r]=x;//栈
    V[x]=true;//表示在栈中，避免非连通更新（如6->2）的情况
    int R=r;
    for(int i=0;i<v[x].size();++i){
        if(!DFN[v[x][i]]){//未被访问过，先访问
            dfs(v[x][i]);
            LOW[x]=min(LOW[x],LOW[v[x][i]]);
        }
        LOW[x]=min(LOW[x],DFN[v[x][i]])
    }
    if(LOW[x]==DFN[x]){
        cnt++;//第cnt个强联通分量
        for(int i=R;i<=r;++i)
            p[st[i]]==cnt;
        r=R-1;//清空栈
    }
}
LOW[x]==DFN[x]->出现强联通分量
维护一个栈

//缩点
for (i=1; i<=m; i++)
  if (p[u[i]]!=p[v[i]])
    add(p[u[i]],p[v[i]]);

例受欢迎的牛
牛群中有一个规定，若A认为B受欢迎，B认为C受欢迎，则A也会认为C受欢迎。
求存在多少牛被每头牛都认为是受欢迎的。
给定牛的头数n以及初始时所有m对形如Ai认为Bi受欢迎。
n<=50000,m<=100000。

Tarjan+缩点，变成拓扑图
缩点之后，若两个点出度为0那么互相不受对方欢迎
如果只有一个点出度为0，这个点一定被所有点都认为受欢迎。
答案就是这个点缩点前牛的个数。

割点

我们称一个点u为这个图的割点，当且仅当删去这个点以及与该点连接的所有边后，这个图不连通。
对该图进行一次Tarjan算法（这里注意在搜索树中把无向边当做有向边看。即LOW[u]=min(LOW[u],DFN[v])(v是u的祖先)的条件变为(v是u的祖先且v不是u的父亲)）这样之后枚举搜索树上的所有边(u,v)，若存在LOW[v]>=DNF[u]，则u是割点。
这个的原理解释不清...这贴一张图吧
2017-10-4 20-38-34.JPG

2-SAT

m个二元组 $<a_i,b_i>$ ，存在 $a_i||b_i$ 或者 $a_i\&\&b_i$ ，判断是否有矛盾。
将每一点列成 $1_x,1_y$
x表示选，y表示不选
例如：
1.如果选了ai，则bi必须选择 1 1 2
2.如果没选ai，则bi必须不选 2 2 3
3.如果选了ai，则bi必须不选 3 1 3
4.如果没选ai，则bi必须选择 4 3 2
判断是否有矛盾
构完图之后，做一次Tarjan，判断是否有x,y在同一个强联通分量中，如果不在就说明是合法的。
QQ截图20171004203152.png

例题

T1

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

求出所有割点，将其它连通块缩点。
对接下来所有点，如果和多个割点相连就不管，只和一个点相连就需要建一个。
然后把点还原为连通块，需要一波乘法原理。

T2

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

拓扑排序裸题。
一个点是连向它的点的最大值+1。

T3

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

以k[i]为边建图，BFS。

T4

给定一个n个点m条带权边的图。
定义一条路径的值为这条路径上经过的边的最小值。
有Q组询问，每组询问形如x到y所有路径的最大值。
n,m,Q<=30000。

由于求最小，先跑最小生成树。
然后用一下倍增LCA。
复杂度O(nlogn)

T5

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

从1点开始BFS，可以对每个点求出最短路，构一颗最短路树，复杂度是O(nm)
如果删的边不在树上就不会有影响。
如果在树上，重新BFS再求最短路。这个操作是O(nm)
其它边是O(1)的，
而对于所有的n个点，复杂度 $O(n^2m)$