解析·NOIP·冷门 CLZ最小环

赐予我力量，去改变我所能改变的;赐予我勇气，去接受我不能改变的;并赐予我智慧，去分辨这两者。

-----安东尼达斯

NOIP的图论题中有一部分是跟图上的环有关的。蒟蒻的我在USACO上刷题时发现了一种（或许）还没有普及的快速最小环算法，拥有极高的效率，可以在求最短路的时间复杂度内求出经过任意一点的最小环大小或权值。作者将它称作Calculate lacework zoomly shortest cyclic，这里暂译作CLZ最小环。

与Floyd求图上最小环不同，CLZ最小环还可以很快捷地求出经过特定点的最小环。

CLZ最小环的思路也极为简单，很容易理解：对于求经过一个点\(s\)的最小环时，即首先进行最短路操作，在进行第一次松弛操作后重新将该点标记为未访问，并重新访问。由于是与最短路同时运作，所以其复杂度几乎取决于最短路算法。当然，CLZ最小环仍有其独立的优化方案。

朴素情况

首先让我们考虑朴素情况，非负带环有向图。对于求最小环中所含的点数，我们只需要将每一条边的权值修改为1，再按上述过程操作即可。

至于如何回退操作，相信不用细讲。我们可以在最短路算法的最前定义一个布尔型变量bool wait初始值为1，在进行完松弛操作后判断wait的状态来决定是否需要将起点重新放入。

void dijkstra(int u){
    bool wait=1;
    /*
    blblblblblbl
    */
    if(wait){
       dis[u]=0x3f3f3f3f,vis[u]=0;//对单个点进行初始化
       q.push(u);//将点重新放入
       wait=0;//设定当前松弛次数
    }
}

函数代码如下

void dijkstra(int u){
	pall note;
	bool wait=1;
	for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0;
	dis[u]=0;vis[u]=1;
	set<pall,cmp> s;
	s.insert(make_pair(u,0));
	for(register int i=0;i<n && s.size();i++){
		set<pall,cmp>::iterator it=s.begin();
		u=it->X;
		s.erase(*it);
		vis[u]=1;
		for(register int j=p[u];~j;j=E[j].next){
			int v=E[j].v;
			int w=E[j].w;
			if(dis[v]>dis[u]+w && !vis[v]){
				s.erase(make_pair(v,dis[v]));
				s.insert(make_pair(v,dis[v]=dis[u]+w));
				note=make_pair(u,v);
			}
		}
		if(wait){
			dis[u]=0x3f3f3f3f;
			vis[u]=0;
			wait=0;
		}
	}
}

无向图

对于无向图来说，若允许经过同一条边多次，则与上述操作无异。但若每条边只能经过一次，则需要一些额外的操作。因为无向图的性质，我们可以知道，从\(u\)到\(v\)的路径权值和与从\(v\)到\(u\)的路径权值和是相等的。因此我们可以考虑判断当前路径的权值\(w\)与上一条路径的权值\(w\)是否相等，并以此来考虑是否选择当前路径。

当然也有更简单的判断方式。若数据量较大，我们只需将等待的wait往后延长一次松弛操作即可。而数据较小时，我们可以直接暴力求解，不在本题的考虑范围之内。

对于普适且较为常规的情况，我们可以先求出点\(S\)连向的边与\(S\)的距离，保存该距离，并枚举每一个距离的总长度即可。

if(dis[u]==w)continue;
/*-----------写法分割线------------*/
if(wait==1 && E[i ^ 1].w==w)continue;
wait++;
int wait=0;
if(wait==1){
	dis[u]=0x3f3f3f3f;
	q.push(u);
	//wait=0;
}

带负权

负环判断

普通的spfa可以直接解决，也可以将所有边权去反，再判断带负权的正环。详情见下文详述。

正环判断

所谓正环有两种定义。一个环上所有边为正，或一个环上权值的和为正。

对于第一种定义，我们只需要在遇见负边时跳过即可。

对于第二种定义，则需要些许变通。我们不再直接修改或操作原边权值，而是再在结构体中声明新的变量将点的数量转化为边权值。如下图，两种边权是不会互相干扰的。



由于有负边权，我们选择使用spfa跑最短路。我们在跑最短路的过程中同时计算两种权值。当且仅当两种边权都有更优解时我们才用新答案替换原有答案（可以稍微思考一下）。当我们按题目给的边权走，使得当前最短路为负数时，我们直接跳过该判断。并不用但担心这里会跳出正确答案，因为由于我们会在每一个点都进行一次spfa寻找操作，所以有且一定有至少一种情况让我们在跑环的过程中边权绝不为负。且这里的为负就跳出也为CLZ最小环算法提供了很好的剪枝。

以下是带负边权的有向图最小环代码

void spfa(int u){
	//额外的，E[i].a记录点的数量转化来的边权,即E[i].a恒等于1
	//ges[u]记录当前最小环内的点数，即a权值维护的最小值
	bool wait=1;
	for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0,ges[i]=0x3f3f3f3f;
	dis[u]=0;vis[u]=1;
	ges[u]=0;
	queue<int> q;
	q.push(u);
	while(!q.empty()){
		u=q.front();
		q.pop();
		vis[u]=0;
		for(register int i=p[u];~i;i=E[i].next){
			int v=E[i].v;
			int w=E[i].w;
			int a=E[i].a;
			if(dis[v]>dis[u]+w && ges[v]>ges[u]+a && dis[u]+w>0){
				ges[v]=ges[u]+a;
				dis[v]=dis[u]+w;
				//cout<<dis[v]<<" "<<dis[u]+w<<endl;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
		if(wait){
			q.push(u);
			dis[u]=0x3f3f3f3f;
			vis[u]=0;
			ges[u]=0x3f3f3f3f;
			wait=0;
		}
	}
}

我们可以发现，其实CLZ最小环只是一种延迟操作的思想。作者只不过是使用了这一思路的一小部分，利用其智慧将最短路的松弛操作分开而已。或许在未来作者会以该思路获得更多灵感，笔者也会持续关注。

最后附上朴素写法的板子

#include<bits/stdc++.h>
#define maxn 3000
#define maxm 5000
#define X first
#define Y second
#define pall pair<int,int>
using namespace std;
inline char get(){
	static char buf[300],*p1=buf,*p2=buf;
	return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	register char c=get();register int f=1,_=0;
	while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
	while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
	return _*f;
}
struct edge{
	int u,v,w,next;
}E[maxm];
struct cmp{
	operator ()(const pall &a,const pall &b)const{
		if(a.Y!=b.Y)return a.Y<b.Y;
		return a.X<b.X;
	}
};
int p[maxn],eid;
inline void init(){
	for(register int i=0;i<maxn;i++)p[i]=-1;
	eid=0;
}
inline void insert(int u,int v,int w){
	E[eid].u=u;
	E[eid].v=v;
	E[eid].w=w;
	E[eid].next=p[u];
	p[u]=eid++;
}
inline void insert2(int u,int v,int w){
	insert(u,v,w);
	insert(v,u,w);
}
int n,m;
int dis[maxn],vis[maxn];
void dijkstra(int u){
	pall note;
	bool wait=1;
	for(register int i=0;i<maxn;i++)dis[i]=0x3f3f3f3f,vis[i]=0;
	dis[u]=0;vis[u]=1;
	set<pall,cmp> s;
	s.insert(make_pair(u,0));
	for(register int i=0;i<n && s.size();i++){
		set<pall,cmp>::iterator it=s.begin();
		u=it->X;
		s.erase(*it);
		vis[u]=1;
		for(register int j=p[u];~j;j=E[j].next){
			int v=E[j].v;
			int w=E[j].w;
			if(dis[v]>dis[u]+w && !vis[v]){
				s.erase(make_pair(v,dis[v]));
				s.insert(make_pair(v,dis[v]=dis[u]+w));
				note=make_pair(u,v);
			}
		}
		if(wait){
			dis[u]=0x3f3f3f3f;
			vis[u]=0;
			wait=0;
		}
	}
}
int u,v,w;
int main(){
	freopen("1.txt","r",stdin);
	init();
	n=read();m=read();
	for(register int i=0;i<m;i++){
		u=read();v=read();w=read();
		insert(u,v,1);
	}
	int ans=0x3f3f3f3f;
	for(register int i=1;i<=n;i++){
		dijkstra(i);
		ans=min(ans,dis[i]);
	}
	cout<<ans<<endl;
	return 0;
}