题解 P4214 【[CERC2015]Juice Junctions】

· · 题解

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

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

由于最大流=最小割,所以最大流一定回\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;
}