【BZOJ2502】清理雪道

    一道最小流的题。设虚拟源汇为s,t（就是把图从无源无汇变成有源有汇的），超级源汇（用于求上下界）ss,st。

    建图：先按常规求上下界网络流的方法建图，连t->s，第一遍求出ss到st的最大流，则t->s边上的流为当前的可行流流量；然后删除与ss，st相连的所有边，删除t->s这条边，连ss->t,s->st，再求一遍ss到st的最大流把第一次可行流的跑多出来的流量跑回去。答案即第一次跑出来t->s边上流量减去第二次跑出来的最大流。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110,maxm=maxn*maxn,inf=~0U>>2;
 
int head[maxn],next[maxm<<1],E[maxm<<1],F[maxm<<1],cur[maxn],Ecnt;
int n,ss,st,s,t,ans;
 
void Add_Edge(int x,int y,int flow) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;F[Ecnt]=0;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;F[Ecnt]=flow;}
 
int InFlow[maxn];
 
void Init()
{
    scanf("%d",&n);
    s=n+1;t=n+2;ss=n+3;st=n+4;Ecnt=1;
    for (int i=1;i<=n;i++)
    {
        int mi,v;scanf("%d",&mi);
        while (mi--) scanf("%d",&v),Add_Edge(i,v,inf),InFlow[i]--,InFlow[v]++;
        Add_Edge(s,i,inf);
        Add_Edge(i,t,inf);
    }
    for (int i=1;i<=n;i++) if (InFlow[i]>0) Add_Edge(ss,i,InFlow[i]);else if (InFlow[i]<0) Add_Edge(i,st,-InFlow[i]);
    Add_Edge(t,s,inf);
}
 
int q[maxn],h[maxn],qhead,qtail;
bool BFS(int S,int T)
{
    memset(h,0,sizeof(h));
    for (int i=1;i<=n+4;i++) cur[i]=head[i];
    q[qhead=qtail=1]=S;
    h[S]=1;
    while (qhead<=qtail)
    {
        int x=q[qhead++];
        for (int i=head[x];i;i=next[i]) if (!h[E[i]] && F[i^1]) q[++qtail]=E[i],h[E[i]]=h[x]+1;
    }
    return h[T];
}
 
int DFS(int x,int T,int flow)
{
    if (x==T) return flow;
    int rest=flow;
    for (int &i=cur[x];i && rest;i=next[i]) if (h[E[i]]==h[x]+1 && F[i^1])
    {
        int d=DFS(E[i],T,min(F[i^1],rest));
        rest-=d;F[i]+=d;F[i^1]-=d;
    }
    if (flow==rest) h[x]=-1;
    return flow-rest;
}
 
int Dinic(int S,int T)
{
    int res=0;
    while (BFS(S,T)) res+=DFS(S,T,inf);
    return res;
}
 
void ReBuild()
{
    for (int i=1;i<=n+2;i++)
    {
        if (E[head[i]]==ss || E[head[i]]==st) head[i]=next[head[i]];
        else for (int j=head[i];j;j=next[j])
            if (E[next[j]]==ss || E[next[j]]==st) next[j]=next[next[j]];
    }
    for (int i=head[t];i;i=next[i]) if (E[i]==s) ans=F[i],F[i]=F[i^1]=0;
    Add_Edge(ss,t,inf);
    Add_Edge(s,st,inf);
}
 
int main()
{
    Init();
    Dinic(ss,st);
    ReBuild();
    ans-=Dinic(ss,st);
    printf("%d\n",ans);
    return 0;
}