BZOJ-2229: [Zjoi2011]最小割

[文章目录]

Description

现给定一张无向图,小白有若干个形如“图中有多少对点它们的最小割的容量不超过x呢”的疑问,小蓝虽然很想回答这些问题,但小蓝最近忙着挖木块,于是作为仍然是小蓝的好友,你又有任务了。
T<=10,n<=150,m<=3000,q<=30

最小割树
找出原图中两个点s,t的最小割,连接s-t,边权为最小割,之后将割开的两个子图分治,递归进行此操作,发现最后连成了一颗树,称为最小割树。
结论:x到y的最小割即为在最小割树上,x到y的路径中边权的最小值。
作用:只需n次dinic,即可求出全图任意两点间的最小割。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300 
#define M 11000
const int inf=0x3f3f3f3f; 
int n,m;
int head[N],to[M],nxt[M],f[M],cnt,mp[N][N];
inline void add(int x,int y,int z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
int s,t,dis[N];
queue<int>q;
bool bfs()
{
    while(!q.empty()) q.pop();
    memset(dis,-1,sizeof dis);
    q.push(s); dis[s]=0; int x,i;
    while(!q.empty())
    {
        x=q.front(); q.pop();
        for(i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
        {
            dis[to[i]]=dis[x]+1;
            if(to[i]==t) return true;
            q.push(to[i]);
        }
    }
    return false;
}
int dinic(int x,int flow)
{
    if(x==t) return flow;
    int xx,tmp=flow;
    for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
    {
        xx=dinic(to[i],min(tmp,f[i]));
        if(!xx) dis[to[i]]=-1;
        f[i]-=xx; f[i^1]+=xx; tmp-=xx;
        if(!tmp) return flow;
    }
    return flow-tmp;
}
int p[N],cg[N],g[N*N],tot;
bool vis[N];
void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&!vis[to[i]]) dfs(to[i]);
}
void solve(int l,int r)
{
    if(l==r) return ;
    s=p[l]; t=p[r];
    int i,j,tmp=0,i1=l,i2=r;
    for(i=2;i<=cnt;i+=2) f[i]=f[i^1]=(f[i]+f[i^1])>>1;
    while(bfs()) tmp+=dinic(s,inf);
    memset(vis,0,sizeof vis);
    dfs(s);
    for(i=1;i<=n;++i) if(vis[i])
        for(j=1;j<=n;++j) if(!vis[j]&&tmp<mp[i][j])
            mp[i][j]=mp[j][i]=tmp;
    for(i=l;i<=r;++i)
    {
        if(vis[p[i]]) cg[i1++]=p[i];
        else cg[i2--]=p[i];
    }
    for(i=l;i<=r;++i) p[i]=cg[i];
    solve(l,i2); solve(i1,r);
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        memset(head,0,sizeof head); cnt=1;
        memset(mp,0x3f,sizeof mp);
        scanf("%d%d",&n,&m);
        int i,j,x,y,z;
        for(i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        for(i=1;i<=n;++i) p[i]=i;
        solve(1,n);
        for(tot=0,i=1;i<=n;++i)
            for(j=i+1;j<=n;++j)
                g[++tot]=mp[i][j];
        sort(g+1,g+tot+1);
        scanf("%d",&z);
        while(z--)
        {
            scanf("%d",&x);
            printf("%d\n",upper_bound(g+1,g+tot+1,x)-g-1);
        }
        puts("");
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注