自动搬运

查看原文

来自洛谷，原作者为

	zsc2003 AFO|枚举碾标算,N^2过百万;暴力出奇迹,骗分最给力!

搬运于2025-08-24 21:57:46，当前版本为作者最后更新于2019-07-22 20:25:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到有大佬用最小割树做的,蒟蒻并不会

这里借助老师的思想写一个不用网络流的做法

由于最大流=最小割,所以最大流一定回$\leq 3$

那么分类讨论一下

使用并查集维护一下

一、若两个点在不同的集合,那么最大流就是0

二、若两个点同一个集合内

使用tarjan缩点一下

1、若两个点不在同一个联通分量内,则易证这两个点的最大流为1

2、若两个点在同一个联通分量内

①若两个点是三联通的,则最大流为3

②否则为2

按照以上方式分类即可

判断两个点是三联通的方式:

若这两个点是三联通的,则整张图中删除任意一条边后进行tarjan缩点,这两个点仍在同一个联通分量内。

所以删除m条边这两个点所在的连通分量的编号是相同的

使用哈希即可方便的判断是否完全相同,这样求出总和即可

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll unsigned long long
using namespace std;
inline int read()
{
	int r,s=0,c;
	for(;!isdigit(c=getchar());s=c);
	for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);
	return s^45?r:-r;
}
const int N=3010,M=4510;
const ll p=19491001;
int n,m;
struct edge
{
	int to,next;
}mem[M<<1];
int head[N],cnt=1;
inline void add(int u,int v)
{
	mem[++cnt].next=head[u];
	mem[cnt].to=v;
	head[u]=cnt;
}
int fa[N],f1,f2;
inline int getfa(int x)
{
	if(fa[x]!=x)fa[x]=getfa(fa[x]);
	return fa[x];
}
int dfn[N],low[N],ti;
int st[N],top;
int dcc[N],co;
bool vis[M<<1];
ll d[N];
void tarjan(int u,int no)
{
	low[u]=dfn[u]=++ti;
	st[++top]=u;
	for(int i=head[u];i>0;i=mem[i].next)
	{
		if(vis[i])continue;
		if((i==no)||((i^1)==no))continue;
		int to=mem[i].to;
		if(!dfn[to])
		{
			vis[i]=vis[i^1]=1;
			tarjan(to,no);
			vis[i]=vis[i^1]=0;
			low[u]=min(low[u],low[to]);
		}
		else
			low[u]=min(low[u],dfn[to]);
	}
	if(low[u]==dfn[u])
	{
		dcc[u]=++co;
		while(st[top]!=u)
			dcc[st[top--]]=co;
		top--;
	}
}
inline void work()
{
	for(int i=1;i<=n;i++)
		d[i]=1ll;
	for(int no=1;no<=m+1;no++)
	{
		memset(low,0,sizeof(low));
		memset(dfn,0,sizeof(dfn));
		ti=0,co=0,top=0;
		for(int i=1;i<=n;i++)
			if(!dfn[i])
				tarjan(i,no<<1);
		for(int i=1;i<=n;i++)
			d[i]=d[i]*p+(ll)dcc[i];
	}
}
inline int calc(int u,int v)
{
	f1=getfa(u),f2=getfa(v);
	if(f1!=f2)//不在一个集合内最大流为0 
		return 0;
	if(dcc[u]!=dcc[v])//不在一个dcc内最大流为1
		return 1;
	if(d[u]==d[v])//用hash判断每次的dcc是否完全相同 
		return 3;/*如果删掉任意一条边,u,v仍在同一个dcc内
	则u,v在同一个三联通分量内,即最大流为3*/
	return 2;//否则最大流为2	
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		fa[i]=i;
	int u,v;
	for(int i=1;i<=m;i++)
	{
		u=read(),v=read();
		add(u,v),add(v,u);
		f1=getfa(u),f2=getfa(v);
		if(f1!=f2)fa[f1]=f2;
	}
	work();
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			ans+=calc(i,j);
	printf("%d\n",ans);
	return 0;
}