FZOJ 2274 二分+有源汇上下界最小流

http://acm.fzu.edu.cn/problem.php?pid=2274

二分差值，求出最小的存在上下界可行流的答案，再跑一次上下界最小流。

这题恶心的地方在于建图从班级流向寝室会TLE，从寝室流向班级就会快很多。

因为只有三层边，dinic里增广次数只有几次，每次dinic复杂度几乎是O（n+m）的。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005,INF=0x3f3f3f3f;
const int mxN=200005,mxM=500005;
int n,m,k;
int du[N];
int ra[N],rb[N],rc[N],rd[N];
int in[N];
int S,T,SS,TT;
int inflow;

struct graph
{
	int S,T;
    int base[mxN],vec[2*mxM],pre[2*mxM],tot;
    int c[2*mxM];
    int d[mxN],q[mxN];
    bool vis[mxN];
    void init()
    {
    	memset(base,0,sizeof(base));
        tot=1;
    }
    void link(int x,int y,int z)
    {
        vec[++tot]=y; pre[tot]=base[x]; base[x]=tot; c[tot]=z;
        vec[++tot]=x; pre[tot]=base[y]; base[y]=tot; c[tot]=0;
    }
    bool bfs()
    {
        int head=0,tail=0;
        memset(d,-1,sizeof(d));
        d[S]=0;
        q[++tail]=S;
        while(head<tail)
        {
            head++;
            int u=q[head];
            for (int now=base[u];now;now=pre[now])
            {
                int v=vec[now];
                if (d[v]==-1&&c[now]>0)
                {
                    d[v]=d[u]+1;
                    q[++tail]=v;
                    if (v==T) return 1;
                }
            }
        }
        return 0;
    }
    int dfs(int u,int flow)
    {
        int r=0;
        if (u==T) return flow;
        for (int now=base[u];now&&r<flow;now=pre[now])
        {
            int v=vec[now];
            if (c[now]>0&&d[v]==d[u]+1)
            {
                int x=min(c[now],flow-r);
                x=dfs(v,x);
                r+=x;
                c[now]-=x;
                c[now^1]+=x;
            }
        }
        if (!r)d[u]=-2;
        return r;
    }
    int dinic()
    {
        int ans=0;
        while(bfs())
            ans+=dfs(S,INF);
        return ans;
    }
}G;

bool pwork(int dif)
{
	G.init();
	memset(in,0,sizeof(in));

	for (int i=1;i<=k;i++)
		G.link(n+rd[i],rc[i],1);

	S=0,T=n+m+3;
	SS=T-2; TT=T-1;
	for (int i=1;i<=n;i++)
	{
		int l=(du[i]-dif+1)/2;
		int r=(du[i]+dif)/2;
		if (l<0) l=0;
		if (r>du[i]) r=du[i];
		if (l>r) return 0;
		G.link(i,TT,r-l);
		in[i]-=l;
		in[TT]+=l;
	}

	for (int i=1;i<=m;i++)
	{
		int l=du[n+i]-rb[i];
		int r=ra[i];
		if (r>du[n+i]) r=du[n+i];
		if (l<0) l=0;
		G.link(SS,n+i,r-l);
		in[SS]-=l;
		in[n+i]+=l;
	}

	inflow=0;

	for (int i=1;i<T;i++)
	{
		if (in[i]>0) G.link(S,i,in[i]),inflow+=in[i];
		if (in[i]<0) G.link(i,T,-in[i]);
	}
	return 1;
}
int maxflow;
bool check(int dif)
{
	if (!pwork(dif)) return 0;
	G.S=S;  G.T=T;
    G.link(TT,SS,INF);
    int tmp=G.dinic();
    return tmp==inflow;
}
int get(int dif)
{
	if (!pwork(dif)) return 0;
	G.S=S;  G.T=T;
	G.dinic();
    G.link(TT,SS,INF);
    return G.dinic();
}

int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(du,0,sizeof(du));
		for (int i=1;i<=m;i++)
			scanf("%d%d",&ra[i],&rb[i]);
		scanf("%d",&k);
		for (int i=1;i<=k;i++)
		{
			scanf("%d%d",&rc[i],&rd[i]);
			du[rc[i]]++;
			du[n+rd[i]]++;
		}

        int l=0,r=0;
        for (int i=1;i<=n;i++) r=max(r,du[i]);
        while(l<r)
		{
			int mid=(l+r)/2;
			if (!check(mid)) l=mid+1;
			else r=mid;
		}
		printf("%d %d\n",r,get(r));
	}
	return 0;
}