GYM102471K All Pair Maximum Flow 做题记录

给定一个 $n$ 个点 $m$ 条边的无向图，每条边有流量 $w_i$，保证其是一个逆时针从 $1$ 到 $n$ 编号的正 $n$ 边形，且边只会在顶点处相交，求 $n$ 个点两两间的最大流之和，对 $998244353$ 取模。

$3\le n\le 2\times 10^5$，$n\le m\le 4\times 10^5$，$0\le w_i\le 10^9$。

由于这是一个平面图，所以最大流=最小割=对偶图最短路。

具体的，从每个顶点向多边形外面引一条射线，则 $s$ 到 $t$ 的最大流相当于对偶图上两区间的点之间的最短路：

考虑多边形外圈权值最小的边 $e$ 及其所在的最小环 $c$：

有一个性质：

• 最短路一定会经过 $c$ 的 $0$ 条或 $2$ 条边；
• 若最短路经过 $c$ 的 $2$ 条边，则一定可以经过 $e$；

第一条显然，因为有进有出，而且不可能走回头路。

第二条是因为 $e$ 在外围，所以通过更换最短路起点或终点，将最短路经过的 $c$ 上的边换成 $e$ 一定不劣。

那么根据这个性质，我们可以每次找到外围边权最小的边 $e$，将 $w_e$ 加到它所在最小环上的其它边上，然后删掉 $e$。不难发现新图最大流不变。

那么不断进行这样的删边操作，最后图会变成一棵树。而树的最大流=最小割就相当于两点间路径上边权最小值，可以快速计算。

时间复杂度 $O(n\log n)$。

具体实现可以考虑建出对偶图。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>

using namespace std;

typedef long long ll;

const int S=200005,p=998244353;

struct node
{
	int x,y;
	ll w;
}ed[S*2];

int n,m;
vector<pair<int,int> > gg[S];
set<pair<int,int> > g[S*4];
bool flg[S*4],vis[S*4];
vector<node> g2;
int fa[S],siz[S];

int fnd(int x)
{
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		if(x>y) swap(x,y);
		ed[i]=(node){x,y,w};
		gg[x].emplace_back(y,i);
	}
	for(int i=1;i<=n;i++) sort(gg[i].begin(),gg[i].end());
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<gg[i].size();j++)
		{
			int u=gg[i][j].second,rb=gg[i][j].first;
			int v=gg[i][j-1].second,p=gg[i][j-1].first;
			if(i==1&&rb==n)
			{
				m++;
				g[u].emplace(m,u);
				g[m].emplace(u,u);
			}
			g[u].emplace(v,v);
			g[v].emplace(u,v);
			while(p!=rb)
			{
				auto tmp=*gg[p].rbegin();
				int v=tmp.second;
				p=tmp.first;
				g[u].emplace(v,v);
				g[v].emplace(u,v);
			}
		}
	}
	priority_queue<pair<ll,int> > q;
	for(int i=1;i<=m;i++)
	{
		if(g[i].size()==1)
		{
			flg[i]=true;
			int id=g[i].begin()->second;
			q.emplace(-ed[id].w,i);
		}
	}
	while(!q.empty())
	{
		auto t=q.top();
		q.pop();
		int u=t.second;
		if(vis[u]) continue;
		ll w=-t.first;
		int fa=g[u].begin()->first;
		for(auto t:g[fa])
		{
			int v=t.first,id=t.second;
			ed[id].w+=w;
			g[v].erase(make_pair(fa,id));
			if(flg[v])
			{
				vis[v]=true;
				if(v!=u)
				{
					int x=ed[id].x,y=ed[id].y;
					ll w=ed[id].w;
					g2.push_back((node){x,y,w});
				}
			}
			else
			{
				m++;
				flg[m]=true;
				g[m].emplace(v,id);
				g[v].emplace(m,id);
				q.emplace(-ed[id].w,m);
			}
		}
	}
	sort(g2.begin(),g2.end(),[&](node x,node y){
		return x.w>y.w;
	});
	for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
	ll ans=0;
	for(auto t:g2)
	{
		int x=fnd(t.x),y=fnd(t.y);
		ll w=t.w;
		if(x==y) continue;
		ans+=w%p*siz[x]*siz[y]%p;
		siz[y]+=siz[x];
		fa[x]=y;
	}
	ans%=p;
	printf("%lld\n",ans);
	return 0;
}