bzoj 2502 清理雪道（有源汇上下界最小流）

2502: 清理雪道

Time Limit: 10 Sec Memory Limit: 128 MB

Description

滑雪场坐落在FJ省西北部的若干座山上。

从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。

由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

Input

输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。接下来的n行，描述1~n号地点出发的斜坡，第i行的第一个数为m (0 <= m < n) ，后面共有m个整数，由空格隔开，每个整数a互不相同，代表从地点i下降到地点a的斜坡。每个地点至少有一个斜坡与之相连。

Output

输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

Sample Input

8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0

Sample Output

下界为1，上界为inf

法一、从超级源点向超级汇点跑一遍dinic，再由普通汇点向普通源点连一条下界为0，上界为inf的边，再由超级源点向超级汇点跑一遍dinic

答案为最后加的那条边的反向边的流量

#include<cstdio>

#include<queue>

#include<algorithm>

#define N 105

#define M 40001

using namespace std;

const int inf=2e9;

int n,a[N],ans;

int src,dec,S,T;

int to[M],next[M],front[N],tot=,cap[M];

int lev[N],cur[N];

queue<int>q;

void add(int u,int v,int w)

{

    to[++tot]=v; next[tot]=front[u]; front[u]=tot; cap[tot]=w;

    to[++tot]=u; next[tot]=front[v]; front[v]=tot; cap[tot]=;

}

bool bfs(int s,int t)

{

    for(int i=;i<=n+;i++) cur[i]=front[i],lev[i]=-;

    while(!q.empty()) q.pop();

    lev[s]=;

    q.push(s);

    int now;

    while(!q.empty())

    {

        now=q.front(); q.pop();

        for(int i=front[now];i;i=next[i])

         if(cap[i]>&&lev[to[i]]==-)

         {

             lev[to[i]]=lev[now]+;

             if(to[i]==t) return true;

             q.push(to[i]);

         }

    }

    return false;

}

int dfs(int now,int t,int flow)

{

    if(now==t) return flow;

    int rest=,delta;

    for(int i=front[now];i;i=next[i])

     if(cap[i]>&&lev[to[i]]>lev[now])

     {

          delta=dfs(to[i],t,min(flow-rest,cap[i]));

          if(delta)

          {

              cap[i]-=delta; cap[i^]+=delta;

              rest+=delta; if(rest==flow) return rest;

         }

     }

    if(rest!=flow) lev[now]=-;

    return rest;

}

int dinic(int s,int t)

{

    while(bfs(s,t)) dfs(s,t,inf);

}

int main()

{

    scanf("%d",&n);

    dec=n+; S=n+;T=n+;

    for(int i=;i<=n;i++) add(i,dec,inf);

    for(int i=;i<=n;i++) add(src,i,inf);

    int x,y;

    for(int i=;i<=n;i++)

    {

        scanf("%d",&x);

        while(x--)

        {

            scanf("%d",&y);

            add(i,y,inf);

            a[y]++; a[i]--;

        }

    }

    for(int i=;i<=n;i++)

     if(a[i]>) add(S,i,a[i]);

     else if(a[i]<) add(i,T,-a[i]);

    dinic(S,T);

    add(dec,src,inf);

    dinic(S,T);

    printf("%d",cap[tot]);

}

法二、先由普通汇点向普通源点连一条下界为0，上界为inf的边，再由超级源点向超级汇点跑一遍dinic，记那条边的流量为okflow

删去那条边，删去超级源点，删去超级汇点，由普通汇点向普通源点跑一遍dinic，得出最大流为a，

答案为okflow-a

#include<cstdio>

#include<queue>

#include<algorithm>

#define N 105

#define M 40001

using namespace std;

const int inf=2e9;

int n,a[N],ans;

int src,dec,S,T;

int to[M],next[M],front[N],tot=,cap[M];

int lev[N],cur[N];

queue<int>q;

void add(int u,int v,int w)

{

    to[++tot]=v; next[tot]=front[u]; front[u]=tot; cap[tot]=w;

    to[++tot]=u; next[tot]=front[v]; front[v]=tot; cap[tot]=;

}

bool bfs(int s,int t)

{

    for(int i=;i<=n+;i++) cur[i]=front[i],lev[i]=-;

    while(!q.empty()) q.pop();

    lev[s]=;

    q.push(s);

    int now;

    while(!q.empty())

    {

        now=q.front(); q.pop();

        for(int i=front[now];i;i=next[i])

         if(cap[i]>&&lev[to[i]]==-)

         {

             lev[to[i]]=lev[now]+;

             if(to[i]==t) return true;

             q.push(to[i]);

         }

    }

    return false;

}

int dfs(int now,int t,int flow)

{

    if(now==t) return flow;

    int rest=,delta;

    for(int i=front[now];i;i=next[i])

     if(cap[i]>&&lev[to[i]]>lev[now])

     {

          delta=dfs(to[i],t,min(flow-rest,cap[i]));

          if(delta)

          {

              cap[i]-=delta; cap[i^]+=delta;

              rest+=delta; if(rest==flow) return rest;

         }

     }

    if(rest!=flow) lev[now]=-;

    return rest;

}

int dinic(int s,int t)

{

    int tmp=;

    while(bfs(s,t))

     tmp+=dfs(s,t,inf);

    return tmp;

}

void del(int x)

{

    for(int i=front[x];i;i=next[i])

     cap[i]=cap[i^]=;

}

int main()

{

    scanf("%d",&n);

    dec=n+; S=n+;T=n+;

    for(int i=;i<=n;i++) add(i,dec,inf);

    for(int i=;i<=n;i++) add(src,i,inf);

    int x,y;

    for(int i=;i<=n;i++)

    {

        scanf("%d",&x);

        while(x--)

        {

            scanf("%d",&y);

            add(i,y,inf);

            a[y]++; a[i]--;

        }

    }

    for(int i=;i<=n;i++)

     if(a[i]>) add(S,i,a[i]);

     else if(a[i]<) add(i,T,-a[i]);

    add(dec,src,inf);

    dinic(S,T);

    int okflow=cap[tot];

    del(T); del(S); cap[tot]=cap[tot-]=;

    printf("%d",okflow-dinic(dec,src));

}

雪道