P1343 地震逃生

· · 题解

这一题一看就是一道网络流最大流。

逃生道路——>水管

学生——>水

教室——>源点

安全地带——＞汇点

最大流的精髓就在反向边 (・◇・)？

基本概念

残量=容量-已流过的量

反向边的流量值=正向流过的总流量，也就是说正向流过多少，反向可以流回多少。

最大流有好几种做法：EK(edmonds-karp) or I S A P or Dicnic......

然额，窝只会EK和ISAP,但是，EK貌似不太行，so 我们选择ISAP。

因为，窝是自学ISAP的，所以代码是从你谷的blog里学来的，应该不算侵权⑧。 ISAP模板

#include<bits/stdc++.h>
using namespace std;
const int inf=2147483647;//inf:最大值 
int cnt=1,head[13000];//cnt:第CNT条边head[i]:第i个点属于第几条边 
int n,m,s,t;//n个点m条边s:源点t:汇点 
inline int Read()
{
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
struct Node
{
    int v;//当前点 
    int next;//连接点 
    int val;//容量 
}node[250000];//node[i]:第i条边的情况 
inline void addedge(int u,int v,int val)
{
    node[++cnt].v=v;
    node[cnt].val=val;
    node[cnt].next=head[u];
    head[u]=cnt;
}
int dep[13000],gap[13000];//dep[i]表示节点i的深度，gap[i]表示深度为i的点的数量 
void bfs()//倒着搜 
{
    memset(dep,-1,sizeof(dep));//把深度变为-1(0会导致gap崩坏) 
    memset(gap,0,sizeof(gap));
    dep[t]=0;//汇点深度为0 
    gap[0]=1;//深度为0的点有1个 
    queue<int>q; 
    q.push(t);//t点入栈 
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=node[i].next)//head[u]:u点所在的边,node[i].next:u点所在的边的下一个点，就这样遍历下去 
        {
            int v=node[i].v;//v为当前边的下一个点 
            if(dep[v]!=-1)  continue;//dep[v]!=-1相当于v点已被遍历||不管 
            q.push(v);
            dep[v]=dep[u]+1;//v点的深度比u点大1 
            gap[dep[v]]++;
        }//直到所有点都被遍历过 
    }
    return;
}//从t到s跑一遍bfs，标记深度
int maxflow;
int dfs(int u,int flow)
{
    if(u==t)
    {
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int i=head[u];i;i=node[i].next)//head[u]:u点所在的边,node[i].next:u点所在的边的下一个点，就这样遍历下去 
    {
        int d=node[i].v;
        if(node[i].val&&dep[d]+1==dep[u])//如果这条边的残量大于0,且没有断层 
        {
            int mi=dfs(d,min(node[i].val,flow-used));//流量 
            if(mi)
            {
                node[i].val-=mi;//正向边-mi 
                node[i^1].val+=mi;//反向边+mi 
                used+=mi;
            }
            if(used==flow)return used;
        }
    }
    //如果已经到了这里，说明该点出去的所有点都已经流过了
    //并且从前面点传过来的流量还有剩余
    //则此时，要对该点更改dep
    //使得该点与该点出去的点分隔开
    --gap[dep[u]];
    if(gap[dep[u]]==0)dep[s]=n+1;//出现断层，无法到达t了
    dep[u]++;//层++ 
    gap[dep[u]]++;//层数对应个数++
    return used; 
}
int ISAP()
{
    maxflow=0;
    bfs();//从t到s跑一遍bfs，标记深度
    while(dep[s]<n) dfs(s,inf);//每走一遍增广路,s的层数会加1,如果一直没有出现断层,最多跑n-dep(刚bfs完时s的深度)条增广路共有n个点 
    return maxflow;
}
int main()
{
    n=Read(),m=Read(),s=Read(),t=Read();
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=Read();
        v=Read();
        w=Read();
        addedge(u,v,w);//正向边 
        addedge(v,u,0);//反向边 
    }  
    printf("%d\n",ISAP());
    return 0;
}

但是,but,这道题并不是只要套上模板就珂以过的，因为，TA让我们算"每批最多能运出多少个学生，x名学生分几批才能运完。",所以，在结尾加上几句话就好了

    int al=ISAP(),time;

    if(al)
    {
        time=x/al;
        if(al*time<x)   time++;
        printf("%d %d\n",al,time);
    }
    else
        printf( "Orz Ni Jinan Saint Cow!\n"); 
    return 0;

附上A C code:

#include<bits/stdc++.h>
#define MAXN 205
#define MAXM 4005
using namespace std;
const int inf=2147483647;//inf:最大值 
int cnt=1,head[MAXN];//cnt:第CNT条边head[i]:第i个点属于第几条边 
int n,m,s,t;//n个点m条边s:源点t:汇点 
inline int Read()
{
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
struct Node
{
    int v;//当前点 
    int next;//连接点 
    int val;//容量 
}node[MAXM];//node[i]:第i条边的情况 
inline void addedge(int u,int v,int val)
{
    node[++cnt].v=v;
    node[cnt].val=val;
    node[cnt].next=head[u];
    head[u]=cnt;
}
int dep[MAXN],gap[MAXN];//dep[i]表示节点i的深度，gap[i]表示深度为i的点的数量 
void bfs()//倒着搜 
{
    memset(dep,-1,sizeof(dep));//把深度变为-1(0会导致gap崩坏) 
    memset(gap,0,sizeof(gap));
    dep[t]=0;//汇点深度为0 
    gap[0]=1;//深度为0的点有1个 
    queue<int>q; 
    q.push(t);//t点入栈 
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=node[i].next)//head[u]:u点所在的边,node[i].next:u点所在的边的下一个点，就这样遍历下去 
        {
            int v=node[i].v;//v为当前边的下一个点 
            if(dep[v]!=-1)  continue;//dep[v]!=-1相当于v点已被遍历||不管 
            q.push(v);
            dep[v]=dep[u]+1;//v点的深度比u点大1 
            gap[dep[v]]++;
        }//直到所有点都被遍历过 
    }
    return;
}//从t到s跑一遍bfs，标记深度
int maxflow;
int dfs(int u,int flow)
{
    if(u==t)
    {
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int i=head[u];i;i=node[i].next)//head[u]:u点所在的边,node[i].next:u点所在的边的下一个点，就这样遍历下去 
    {
        int d=node[i].v;
        if(node[i].val&&dep[d]+1==dep[u])//如果这条边的残量大于0,且没有断层 
        {
            int mi=dfs(d,min(node[i].val,flow-used));//流量 
            if(mi)
            {
                node[i].val-=mi;//正向边-mi 
                node[i^1].val+=mi;//反向边+mi 
                used+=mi;
            }
            if(used==flow)return used;
        }
    }
    //如果已经到了这里，说明该点出去的所有点都已经流过了
    //并且从前面点传过来的流量还有剩余
    //则此时，要对该点更改dep
    //使得该点与该点出去的点分隔开
    --gap[dep[u]];
    if(gap[dep[u]]==0)dep[s]=n+1;//出现断层，无法到达t了
    dep[u]++;//层++ 
    gap[dep[u]]++;//层数对应个数++
    return used; 
}
int ISAP()
{
    maxflow=0;
    bfs();//从t到s跑一遍bfs，标记深度
    while(dep[s]<n) dfs(s,inf);//每走一遍增广路,s的层数会加1,如果一直没有出现断层,最多跑n-dep(刚bfs完时s的深度)条增广路共有n个点 
    return maxflow;
}
int main()
{
    n=Read(),m=Read(),s=1,t=n;
    int x=Read();
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=Read();
        v=Read();
        w=Read();
        addedge(u,v,w);//正向边 
        addedge(v,u,0);//反向边 
    }
    int al=ISAP(),time;

    if(al)
    {
        time=x/al;
        if(al*time<x)   time++;
        printf("%d %d\n",al,time);
    }
    else
        printf( "Orz Ni Jinan Saint Cow!\n"); 
    return 0;
}

完结✿✿ヽ(°▽°)ノ✿

update 2020.4.2

新增一种算法EK。as we know,EK是edmonds-karp的简写。

Edmonds-Karps增广路算法的时间复杂度为O(nm^2)。

然而在实际运用中则远远达不到这个界，

效率较高，一般能处理10^3~10^4规模的网络

               ——李煜东《算法竞赛进阶指南》

先贴模板

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define For(i,k,j) for(register int i=(k);i<=(j);i++)
#define INF 2147483647
using namespace std;
const int MAXN=10001;
const int MAXM=100001;
int g[MAXN][MAXN]; //g[u][v] : u -> v 还可以流的量 (正向图) 
int pre[MAXN]; // 记录每个点的前驱
bool vis[MAXN]; // 记录每个点是否被访问过 
int n,m;
inline bool bfs(int s,int t)//经典BFS 
{
    //新的开始 
    mst(pre,-1);//重新计算pre[] 
    mst(vis,0);//重新记录vis[] 
    queue<int>q;//新建队列 
    vis[s]=true;//源点已被遍历 
    q.push(s);//压入队列 
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        For(i,1,n) 
        {
            if(!vis[i]&&g[now][i]>0)//如果这个点没被遍历到,且now和i有管道 
            {
                vis[i]=true;//当前点已被访问 
                pre[i]=now;//记录i点的前一个点是now 
                if(i==t)//如果i点是汇点,那么,一条路径产生 
                    return 1;
                q.push(i);//else,继续搜 
            }
        }
    }
    return 0;//所有路径都被遍历完了 
}
inline int EK(int s,int t) 
{
    int v,u,d,maxflow=0;
    while(bfs(s,t)) 
    { //可以增广 
        v=t,d=INF;//找可增量d ,d为当前流量 
        while(v!=s)//回溯 
        {
            u=pre[v]; // u记录v的前驱 
            d=min(d,g[u][v]);  // d 和当前边（正向边）还可以流过去的量取最小值->能流多少 
            v=u;//v=前一个点 
        }
        maxflow+=d;//最大流量 
        v=t;//Do it again
        while(v!=s)//回溯 
        {
            u=pre[v];// u记录v的前驱 
            g[u][v]-=d; //网络中的正向边剩下可以流的量减少d 
            g[v][u]+=d; //网络中的反向边剩下可以流的量增加d
            v=u;
        }
    }
    return maxflow;
}
int main()
{
    scanf("%d%d",&n,&m);//n为点数，m为边数 
    int s,t;//源点&汇点 
    scanf("%d%d",&s,&t);
    For(i,1,m) 
    {
        int u,v,w;//起点,终点,管道流量 
        scanf("%d%d%d",&u,&v,&w); 
        g[u][v]+=w;//建图 
    }
    printf("%d\n",EK(s,t));
    return 0;
}

大家可以先看注释，用的是邻接矩阵。

这里就将详细讲一个部分

if(!vis[i]&&g[now][i]>0)//如果这个点没被遍历到,且now和i有管道
$!vis[i]$表示当前点木有被遍历（此次BFS） RT![](https://cdn.luogu.com.cn/upload/image_hosting/k8mmsvy0.png?x-oss-process=image/resize,m_lfit,h_170,w_225) ——>![](https://cdn.luogu.com.cn/upload/image_hosting/b2rqx69g.png?x-oss-process=image/resize,m_lfit,h_170,w_225) 设中间一点为a，左上为x，右上为b 那么我们随机给管道的容量赋值，在最优情况下，$S-A-X-Y-T$的流量不可能大于$S-A-T$的流量。 ------------ $AC$ $code 

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define For(i,k,j) for(register int i=(k);i<=(j);i++)
#define INF 2147483647
using namespace std;
const int MAXN=10001;
const int MAXM=100001;
int g[MAXN][MAXN]; //g[u][v] : u -> v 还可以流的量 (正向图) 
int pre[MAXN]; // 记录每个点的前驱
bool vis[MAXN]; // 记录每个点是否被访问过 
int n,m;
bool bfs(int s,int t)//经典BFS 
{
    //新的开始 
    mst(pre,-1);//重新计算pre[] 
    mst(vis,0);//重新记录vis[] 
    queue<int>q;//新建队列 
    vis[s]=true;//源点已被遍历 
    q.push(s);//压入队列 
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        For(i,1,n) 
        {
            if(!vis[i]&&g[now][i]>0)//如果这个点没被遍历到,且now和i有管道 
            {
                vis[i]=true;//当前点已被访问 
                pre[i]=now;//记录i点的前一个点是now 
                if(i==t)//如果i点是汇点,那么,一条路径产生 
                    return 1;
                q.push(i);//else,继续搜 
            }
        }
    }
    return 0;//所有路径都被遍历完了 
}
inline int EK(int s,int t) 
{
    int v,u,d,maxflow=0;
    while(bfs(s,t)) 
    { //可以增广 
        v=t,d=INF;//找可增量d ,d为当前流量 
        while(v!=s)//回溯 
        {
            u=pre[v]; // u记录v的前驱 
            d=min(d,g[u][v]);  // d 和当前边（正向边）还可以流过去的量取最小值->能流多少 
            v=u;//v=前一个点 
        }
        maxflow+=d;//最大流量 
        v=t;//Do it again
        while(v!=s)//回溯 
        {
            u=pre[v];// u记录v的前驱 
            g[u][v]-=d; //网络中的正向边剩下可以流的量减少d 
            g[v][u]+=d; //网络中的反向边剩下可以流的量增加d
            v=u;
        }
    }
    return maxflow;
}
int main()
{
    scanf("%d%d",&n,&m);//n为点数，m为边数 
    int s=1,t=n;//源点&汇点 
    int x;
    scanf("%d",&x);
    For(i,1,m) 
    {
        int u,v,w;//起点,终点,管道流量 
        scanf("%d%d%d",&u,&v,&w); 
        g[u][v]+=w;//建图 
    }
    int al=EK(s,t),time;

    if(al)
    {
        time=x/al;
        if(al*time<x)   time++;
        printf("%d %d\n",al,time);
    }
    else
        printf( "Orz Ni Jinan Saint Cow!\n"); 
    return 0;
}