【全程NOIP计划】图论算法

2021-08-05 14:09:14

【全程NOIP计划】图论算法

最短路算法

常用的最短路算法SPFA,Dijkstra,Floyd算法

最短路问题，就是对于有权图的两个点，找到一条连接两个点的路径，使得路径的权值和最小

在说最短路算法之前，必须了解松弛的概念

其实n简单，如果$a \rightarrow b+b \rightarrow c$的距离比$a \rightarrow c$的小，那么就可以用前者代替a到c的距离

各种各样最短路实际上就是不断做松弛操作

Floyd

可以求出图中任意两点的最短路，过程很简单

首先枚举松弛操作的中间点，再枚举松弛的左右两个点，然后做松弛操作

由于Floyd算法暴力枚举的特性，所以用邻接矩阵很方便

很显然，复杂度为$O(n^3)$

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

正确性

怎么证明正确性？

对于任意两个点之间的最短路，假设有m个节点那么m一定小于n，因为重复经过同样的点没有意义（除非有负环，但是如果有负环最短路就没有意义，因为可以通过刷负环来刷最短路）

那么这m个点在外层循环都会被枚举一次，接着内层的两重循环一定会枚举到这个点在最短路上相邻的两个点

这个点被松弛之后，我们就可以认为它已经不在最短路上了，因为此时的$a \rightarrow b \rightarrow c$和$a \rightarrow c$是一样的

外层循环做完之后，两个点之间的所有m个点也都被消除完了，这两个点的距离就是最短路

易错点

有一个易错点，就是三个循环的顺序不要搞错了

先枚举中间，再枚举两边

因为，如果左边先枚举，那么n次循环之后，松弛的点对都是从左边出发的，如果没有恰好沿着路径的顺序去枚举中间的点，就无法松弛整条路径

有一个神奇的结论，只要Floyd整个过程连续做三遍，不管三个循环是什么顺序，跑出来的结果都是对的，但是不建议使用，主要是慢啊

作用

裸的最短路实际上用的不多，用到了也很简单，基本上是看做一个工具来用

Floyd实际上还可以处理除了最短路以外其他的问题

P2419 Cow Contest S

思路

拓扑排序可以，但是Floyd也可以

这样点很少，边很多的图就很适合使用Floyd

如果用$e[i][j]$表示能不能推出i<j的关系，如果$e[i][k]=1且e[k][j]=1$，那么$e[i][j]=1$

这样我们就可以处理出任意两点间的大小关系，有或者没有

然后如果对于一个点，我们能确定剩下所有点和它的大小关系

那么这个点的排名就被确定了

如果一个点，对于其他任何一个点都能推出它的关系，然后它的排名就确定了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n,m;
int e[105][105];
void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                e[i][j]|=(e[i][k]&e[k][j]);//用floyd来解决直接的关系 
}
int main()
{
    cin>>n>>m;
    int l,r;
    while(m--)
    {
        cin>>l>>r;
        e[l][r]=1;
    }
    floyd();
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int mark=1;
        for(int j=1;j<=n;j++)
            if(j!=i&&e[j][i]==0&&e[i][j]==0)//如果有谁不能确定 
            {
                mark=0;
                break;
            }
        cnt+=mark;
    }
    cout<<cnt<<endl;
    return 0;
}

P2888 Cow Hurdles S

思路

让我想到了营救那道题目

实际上就是二分答案加判断

但是用Floyd处理dp关系可以更简单的做这个题目

$e[i][j]$表示从i到j经过的路径中，最小的最大栏杆高度

容易得到类似于Floyd的关系

也就是说如果走$i \rightarrow k \rightarrow j$的路线，那么栏杆的最大高度为$max(e[i][k],e[k][j])$

如果这个最大值小于$i \rightarrow j$之间的最大值，那么就可以更新这个最小的最大值

也就是先用$O(n^3)$来处理一个Floyd，然后再用$O(t)$处理答案

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=305;
int n,m,T;
int a[maxn][maxn];
int main()
{
	memset(a,20,sizeof(a));
	cin>>n>>m>>T;
	for(int i=1;i<=m;i++)
	{
		int s,e,h;
		cin>>s>>e>>h;
		a[s][e]=h;
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			a[i][j]=min(a[i][j],max(a[i][k],a[k][j]));
	while(T--)
	{
		int l,r;
		cin>>l>>r;
		if(a[l][r]!=336860180)
		cout<<a[l][r]<<'\n';
		else
		cout<<-1<<'\n';
	}
	return 0;
}

P2047 社交网络

思路

这道题目和前两道题目差不多，只不过除了求i到j的路径数量，还要求i经过k到j的路径数量

最短路径比较好求，如果$e[i][k]和e[k][j]$更新了$e[i][j]$的话，让$cnt[i][j]=cnt[i][k]*cnt[k][j]$就可以了

如果$e[i][k]+e[k][j]=e[i][j]$那么还要让$cnt[i][j]+=cnt[i][k]*cnt[k][j]$

因为数据量过小，所以这样来表示是可以的，主要运用的是乘法原理

题目个每个点求$\sum_{s!=v,t!=v}c(s,t,v)c(s,t)$

那么就先跑Floyd，然后枚举每个点，再枚举s和t，用$cnt[s][v]*cnt[v][t]/cnt[s][t]$计算就可以了

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(e[i][k]+e[k][j]<e[i][j])
                {
                    e[i][j]=e[i][k]+e[k][j];
                    cnt[i][j]=cnt[i][k]*cnt[k][j];
                }
                else if(e[i][j]+e[k][j]==e[i][j])
                {
                    cnt[i][j]+=cnt[i][k]*cnt[k][j];
                }
            }
}
int main()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            e[i][j]=INF;
        e[i][i]=0;
    }
    int l,r,v;
    while(m-->0)
    {
        cin>>l>>r>>v;
        e[l][r]=v;
        e[r][l]=v;
        cnt[l][r]=1;
        cnt[r][l]=1;
    }
    floyd();
    for(int k=1;k<=n;k++)
    {
        double ans=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(cnt[i][j]&&e[i][k]+e[k][j]==e[i][j])
                    ans+=(double)(cnt[i][k]*cnt[k][j]/cnt[i][j]);
        printf("%.3lf",ans);
    }
}

Bellman-Ford

这是一个单源最短路算法

也就是能求出从某个点出发到剩下所有点的最短路

这个算法用$dis[v]$表示从s到v的距离

算法总共进行n-1轮，每轮枚举所有的边u到v，来做s到u到u的松弛操作

不难理解，第一轮会求出和s间距一条边的最短路，第二轮会求出间距小于等于2条边的最短路，第n-1轮回求出间距小于等于n-1条边的最短路

由于最短路最多有n-1条边，所以n-1轮之后每个点都求到了真正的最短路

显然这个算法的复杂度是$O(NM)$的，n是点数，m是边数

显然这个算法适合直接结构体来存边，也就是边表

void bellman_ford()
{
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    dis[s]=0;
    for(int k=1;k<n;k++)
    {
        for(int i=1;i<=ecnt;i++)
            if(dis[e[i].x]+e[i].v<dis[e[i].y])
                dis[e[i].y]=dis[e[i].x]+e[i].v;
    }
}

SPFA

上面的一个算法有一个优化，实际上就是spfa

我们每轮操作其实并不一定要把所有的边都松弛一遍

因为有一些店在上一轮之后最短路并没有发生变化，那么从这个点出发的边做松弛也一定没有变化

所以我们不再枚举n-1轮，而是用一个队列，表示刚刚发生过变化，准备要进行松弛的点

每次从队列里拿出一个点，然后枚举这个点的出边并进行松弛，如果出点的值边了，就把出点也加入队列

一个进一步的优化用$flag[v]$表示点v是否在队列里，如果已经在了，那显然是不用重复进队的

显然一开始就应该把s放进队列，然后从s开始松弛

也是用邻接链表来村边

void spfa()
{
    for(int i=1;i<=n;i++)
        flag[i]=false;
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    dis[s]=0;
    q[++head]=s;
    for( ;tail<=head; ++tail)
    {
        flag[q[tail]]=0;
        for(int i=1)
    }
}

复杂度

时间复杂度为$O(VE)$，有的时候并不比Bellman-Ford更快

作用

但是spfa并不是一无是处，当图中有负环的时候，Dijkstra这种纯粹求最短路的算法就挂了

因为负环实际上意味着图中没有最短路

而spfa有三种方式来判断是否存在负环:

1.用$cnt[v]$来表示从s到v的最短路经过了多少个点，如果u到v送出了s到v，那么就让$cnt[v]$更新为$cnt[u]+1$，之前提到过，一个正常的最短路不应该有超过n个点的，因此当$cnt[v]>n$的时候有内鬼，终止交易

2.统计进队次数，一个点如果入队大于n次

3.dfs班也很简单，如果一个点被松弛了，就直接递归进这个点去松弛别人就可以了。如果一个点递归了一圈又回到自己了，显然有负环。一般第二种方法比第一种方法快一点，而第三种方法比前两种都要快。spfa判负环只能判有没有，不能找哪里，如果要找哪里，要用tarjan算法

P3199 最小圈

思路

问题实际上是求$C=\sum w[i]/k$，其中i是边，$w[i]$是边权，k是边数

问题显然存在二分单调性，也就是如果答案太大，那么不符合最小的要求，但是一定可以找出来一个圈，使得比值小于等于这个答案，如果答案太小，那么一定找不到一个圈，使得比值满足这个答案

那么就可以二分答案ans，如果不存在$\sum w[i]/k \le ans$，则答案小，否则答案大

把这个式子变一下，就得到$\sum w[i]-k*ans=\sum(w[i]-ans) \le 0$

需要注意，负圈不一定是要每条边都小于0，而是只要权值和小于0的就可以刷最短路

所以满足$\sum(w[i]-ans)\le 0$的圈实际上就是一个负圈，因为答案是浮点数，所以$<0和 \le0 $的区别不大

那么枚举出答案ans后给每个边权都减去ans，然后spfa判负环就可以了

这个实际上是一个01分数规划的过程

复杂度上线为$O(nmlogw)$，比较危险

Dijkstra

只要出现单源最短路一定要卡spfa的今天，单源最短路的最佳解法就是Dijkstra

实际上如果用stl的优先队列来写，Dijkstra也不会比spfa复杂到哪里去

Dijkstra其实就是一个堆优化的spfa

spfa每次是从已经准备要松弛别人的点中选出某一个，而Dijkstra则是直接使用优先队列贪心地从中选出dis最小的那个

至于这个贪心的全局最优的证明，可以使用归纳法严格证明

每条边至多被访问一次，所以每个点的松弛次数不会超过边数

所以Dijkstra的时间复杂度为$O(MlogN)$

另一种理解

Dijkstra的思路其实是每次从dis中挑出dis最短的那个，之前没有被挑过的点出来松弛

Dijkstra实际上有一个$O(nm)$的做法，就是直接用for循环去找这个最短的的点，这也是为什么会有堆优化的Dijkstra的这种说法

本质上是用堆来维护dis数组的，但是要注意

不能直接对dis建堆，然后随着松弛操作改堆里的数据

如果直接改堆的数据，会破坏堆的结构，导致堆不能完成它应有的功能

因此还要没松弛一次就把出点入堆，然后出堆的时候去更新dis

void dijkstra()
{
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    dis[s]=0;
    size=0;
    push((nod){x,0});
    while(size)
    {
        while(size&&heap[1].y>dis[heap[1].x]) pop();
        if(!size) break;
        x=heap[1].x;
        dis[x]=heap[1].y;
        pop();
        for(int i=link[x];i;i=e[i].next)
            if(dis[x]+e[i].v<dis[e[i].y])
            {
                dis[e[i].y]=dis[x]+e[i].v;
                push((node){e[i].y,dis[e[i].y]});
            }
    }
}

P2837 Milk Pumping G

思路

这个题看上去有二分单调性，又涉及到分数，似乎是分数规划

实际上并没有这么复杂，因为n很小，流量的上线也很小

所以直接枚举路径的流量，流量确定之后最大化流量/花费，实际上就是最小化花费

于是就可以跑Dijkstra，要求流量大于等于枚举的流量的边才能参与松弛就行了

int dijkstra(int y)
{
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    dis[1]=0;
    size=0;
    push((nod){1,0});
    while(size)
    {
        while(size&&heap[1].y>dis[heap[1].x]) pop();
        if(!size) break;
        x=heap[1].x;
        dis[x]=heap[1].y;
        pop();
        for(int i=link[x];i;i=e[i].next)
            if(e[i].w>=y&&dis[x]+e[i].v<dis[e[i].y])
            {
                dis[e[i].y]=dis[x]+e[i].v;
                push((node){e[i].y,dis[e[i].y]});
            }
    }
    return dis[n];
}
int main()
{
    ……
    dounble ans=0;
    for(int i=1;i<=1000;i++)
        ans=max(ans,(double)i/dij(i));
    printf("%lld\n",(long long)(ans*1e6));
    ……
}

最短路建模

差分约束

差分约束系统就是给你一堆变量，然后给你一堆形如$a_i-a_j \le c$的不等式

像这样两个变量相减的形式就叫做差分，一堆变量相减就是差分系统

差分约束能告诉你差分系统中，任意两个变量最多是多少，或者是最少是多少

做法

如果有a1-a2<=b,a2-a3<=d,a1-a3<=e

假设要求a1-a3的范围，我们发现除了a1-a3<=e的条件之外，还有a1-a2+a2-a3=a1-a3<=b+d

那么如果b+d<=e,a1-a3就<=b+d,否则a1-a3<=e

发现了没，这个操作和最短路的松弛操作特别像

我们用$e[i][j]$来表示$a_i-a_j\le e[i][j]$，那么不难发现，对于一个中间点k，我们有$e[i][j]=min(e[i]][j],e[i][k]+e[k][j])$，于是我们就用一个最短路的模型表示一个差分约束系统，然后就可以用最短路算法解出想要的变量的差分关系

有的人就会问，如果同时出现左边右边符号颠倒的情况怎么办，一般就可以把符号和两个数的位置变化一下，一般不会出现变化不了的情况

还有一种题型就是判断有没有解，我们要考虑什么情况下无解，情况有很多，但是可以转化为一个情况，就是a-b<=c且a-b>=d而且c<d,可以看成c-d<0，这就意味着一条循环约束出现了负环，如果常规差分约束建完图之后有负环，那么就无解了

模板代码

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <queue>#define int long long using namespace std;const int maxn=50005;struct edge{	int e,next,val;}ed[maxn*2];int en,first[maxn];void add_edge(int s,int e,int val){	en++;	ed[en].next=first[s];	first[s]=en;	ed[en].e=e;	ed[en].val=val;}int n,m;int d[maxn],num[maxn];bool vis[maxn];queue <int> q;bool spfa(int x){	d[x]=0;	q.push(x); 	vis[x]=true;	num[x]++;	while(q.size())	{		int x=q.front();		q.pop();		vis[x]=false;		for(int i=first[x];i;i=ed[i].next)		{			int e=ed[i].e,val=ed[i].val;			if(d[e]>d[x]+val)			{				d[e]=d[x]+val;				if(!vis[e])				{					q.push(e);					vis[e]=true;					num[e]++;					if(num[e]==n+1)					return false;				}			}		}	}	return true; }signed main(){	cin>>n>>m;	for(int i=1;i<=n;i++)	d[i]=2147483647;	for(int i=1;i<=m;i++)	{		int x,y,z;		cin>>x>>y>>z;		add_edge(y,x,z);	}	for(int i=1;i<=n;i++)	add_edge(n+1,i,0);	if(!spfa(n+1))	{		cout<<"NO"<<'\n';		goto end;	}	for(int i=1;i<=n;i++)	cout<<d[i]<<" ";	end: ;	return 0;}

P1993 小k的农场

思路

直接差分约束系统，判断是否有解就可以了

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <queue>#define int long long using namespace std;const int maxn=50005;struct edge{	int e,next,val;}ed[maxn*2];int en,first[maxn];void add_edge(int s,int e,int val){	en++;	ed[en].next=first[s];	first[s]=en;	ed[en].e=e;	ed[en].val=val;}int n,m;int d[maxn],num[maxn];bool vis[maxn];queue <int> q;bool spfa(int x){	d[x]=0;	q.push(x); 	vis[x]=true;	num[x]++;	while(q.size())	{		int x=q.front();		q.pop();		vis[x]=false;		for(int i=first[x];i;i=ed[i].next)		{			int e=ed[i].e,val=ed[i].val;			if(d[e]>d[x]+val)			{				d[e]=d[x]+val;				if(!vis[e])				{					q.push(e);					vis[e]=true;					num[e]++;					if(num[e]==n+1)					return false;				}			}		}	}	return true; }signed main(){	cin>>n>>m;	memset(d,0x3f,sizeof(d));	for(int i=1;i<=m;i++)	{		int op;		cin>>op;		if(op==1)		{			int a,b,c;			cin>>a>>b>>c;			add_edge(a,b,-c);		}		else if(op==2)		{			int a,b,c;			cin>>a>>b>>c;			add_edge(b,a,c);		}		else		{			int a,b;			cin>>a>>b;			add_edge(a,b,0);			add_edge(b,a,0);		}	}	for(int i=1;i<=n;i++)	add_edge(n+1,i,0);	if(!spfa(n+1))	{		cout<<"No"<<'\n';		return 0;	}	cout<<"Yes"<<'\n';	return 0;}

P3275 糖果

思路

跟上一道题目一样差不多，处理一下差分约束系统

a不比b少就是a>=b

a比b少怎么办？

实际上就是a<b等价于a<=b-1

于是a比b少表示为b-a>=1

现在约束能建了，问题是要求总数最小

可以建立一个抽象节点，表示0颗糖的基准线

然后抽象点往所有点约束为1的边，表示每人至少分一颗糖

这里需要注意，由于求的是最小值，约束是a-b>=c，因此这里求的是最长路，要找出最大的那个下限

最后所有人dis就是不得不满足的下限，然后就能得到答案了

传递闭包

传递闭包的数学概念比较抽象，不太好懂，但是做出来很简单

简单说就是，两个关系i-->k和k-->j可以复合出一个新关系i-->j，这就是传递性

给你一个集合，集合里定义了一个关系i-->j，再定义一个关系i-->j，满足：

1.对于所有满足i-->j,使得i能通过-->的复合关系连接到j，但是不满足i-->j

2.除此之外不存在i和j，使得i能通过-->的复合关系链接到j，但是不满足i-->j

精简版说法，就是传递闭包是关系的极大生成集，因为

1.如果a是b的祖先，那么a肯定是b的父母的父母的父母的……

2.不存在如果a是b父母的父母的父母的……,我们就不能称a为b的祖先的情况

实际上还是有点难理解，但是直接看怎么做吧

对于一个邻接矩阵e，$e[i][j]=0$不满足关系i-->j，$e[i][j]=1$表示满足关系i-->j

然后我们对e做与操作的Floyd，也就是松弛操作为$e[i][j]=e[i][k] and[k][j]$

就这？对，我们之前实际上遇到了一个差不多的例题

强连通分量

强连通分量指的是图的一个极大的子图，满足图内任意两点内任意两点之间可以相互到达

需要注意的是，强连通分量的概念是针对有向图的，无向图没有强连通分量的说法，因为对于无向图，只要是一个连通图就能任意互相到达

强连通分量分成两个部分第一个是任意两个点可以相互到达，这个比较好理解

比如完全图，也就是任意两个点都连接两个方向的边

再比如一个有向环，也满足这个条件

而极大的子图就是说，再加入原图中的任意一个点以及这个点的边到这个子图内，都不能满足互相到达的条件

比如一个完全图子完全图，虽然能互相到达，但是不是极大的

Tarjan算法

求一个图的强连通分量一般用tarjan算法，这里的tarjan算法只指dfs树，也就是dfn-low的那一套理论

首先对于任意一个有向图，我们显然可以用dfs来遍历整个图，每个点只经过一次，并不用管所有点都经过没，那么按照dfs递归的关系，把遍历过程画出来，就是一个dfs树

tarjan在dfs树的基础上定义了dfn和low的概念

dfn就是dfs过程被访问到的顺序

而low表示的是这个点能到达的所有点中，dfn最小的点

tarjan算法首先用一个栈按顺序记录dfs遍历过的点，同时计算dfn和low，每当发现一个点的dfn等于low，那么就把这个点以及栈中之后的所有点弹出来，作为一个强连通分量

void tarjan(int x,int fa){    vis[x]=true;    dfn[x]=low[x]=++dfs_cnt;    s[++top]=x;    for(int i=link[x];i;i=e[i].next)    {        if(!dfn[e[i].y])        {            tarjan(e[i].y,x);            low[x]=min(low[x],low[e[i].y]);        }        else if(vis[e[i].y])            low[x]=min(low[x],dfn[e[i].y]);    }    if(dfn[x]==low[x])    {        grouP_cnt++;        int temp;        do{            temp=s[top--];            group[temp]=group_cnt;            vis[temp]=false;        }while(temp!=x)    }}

正确性

为什么？

对于子图的一个点，如果这个点可以到达任意一个点，而任意一个点也可以到达这个点，我们就说这个子图是任意两点互相到达的

在tarjan算法中，这个点就是dfn等于low的点

我们注意到，在tarjan算法中，这个点就是dfn等于low的点

我们注意到，在tarjan算法中，只要$dfn[x]=low[x]$，那么x就会被弹出来，因此对于一个点x的子树中的点y，只有两种情况：要么已经被弹出来了，要么$low[y]=low[x]$

不可能$low[y]<low[x]$，因为x可以到y，所以y能到的x也能到，那么应该$low[x]\le low[y]$才对

而如果$low[y]>low[x]$，那么到回溯到$low[y]$对应的那个点的时候，y就被弹出栈了

所以栈里面留下来的也一定都能到达x

同时显然x也能到达它的子节点们

因此当$dfn[x]=low[x]$的时候，我们就说x的子树内任意互达

同时这些子树上的点往上最多只能到达x，到不了子树外面的点

因此把任意子树外的点加进来，都会破坏任意互达的条件

再来看为$dfn[y]=low[y]$而被提前弹出栈的的y的子树的点

这些碘同样往外最多只能到达y，到达不了x，因此把y子树中的点加进来也不能满足任意互达的条件

所以tarjan算法找到的点的集合，当然也包括这些点之间的边的集合，是强联通分量

P2341 最受欢迎的牛

思路

我们发现对于一个强联通分量内的牛的机会是相同的，要么一起当明星，要么都当不了明星

因为团体内的任意一头牛会爱慕别的牛，如果团体外的所有牛都爱它，那么就会传递到剩下的所有牛的身上

因此我们可以先做tarjan缩点，把一个强连通分量的牛看成一个整体来考虑

原来牛之间的边要转化为团体间的边

这是我们发现，缩点之后的图变成了一个DAG

前面我们提到过，环是强连通分量，因此如果图中还有环，显然还可以继续缩点

因此把所有强连通分量都缩完的图一定是一个DAG

如果整个DAG只有一个点的出度为n，那么显然所有的点都可以到达这个点

所以当我们缩完点之后发现DAG中只有一个点出度为0，那么我们说这个点中的所有的奶牛都可以当明星

码农公寓

【全程NOIP计划】图论算法

最短路算法

Floyd

正确性

易错点

作用

P2419 Cow Contest S

思路

P2888 Cow Hurdles S

思路

P2047 社交网络

思路

Bellman-Ford

SPFA

复杂度

作用

P3199 最小圈

思路

Dijkstra

另一种理解

P2837 Milk Pumping G

思路

最短路建模

差分约束

做法

P1993 小k的农场

思路

P3275 糖果

思路

传递闭包

强连通分量

Tarjan算法

正确性

P2341 最受欢迎的牛

思路

相关文章