洛谷 P1343 地震逃生 题解【网络流】【最大流】

作者: wjyyy 分类: 图论,网络流,解题报告 发布时间: 2018-05-20 19:42

点击量:44

考试时间 2018/5/20

题目描述

汶川地震发生时,四川**中学正在上课,一看地震发生,老师们立刻带领x名学生逃跑,整个学校可以抽象地看成一个有向图,图中有n个点,m条边。1号点为教室,n号点为安全地带,每条边都只能容纳一定量的学生,超过楼就要倒塌,由于人数太多,校长决定让同学们分成几批逃生,只有第一批学生全部逃生完毕后,第二批学生才能从1号点出发逃生,现在请你帮校长算算,每批最多能运出多少个学生,x名学生分几批才能运完。

输入输出格式

输入格式:

第一行3个整数n,m,x(x<2^31,n<=200,m<=2000);以下m行,每行三个整数a,b,c(a1,a<>b,0描述一条边,分别代表从a点到b点有一条边,且可容纳c名学生。

输出格式:

两个整数,分别表示每批最多能运出多少个学生,x名学生分几批才能运完。如果无法到达目的地(n号点)则输出“Orz Ni Jinan Saint Cow!”

输入输出样例

输入样例#1:
6 7 7
1 2 1
1 4 2
2 3 1
4 5 1
4 3 1
3 6 2
5 6 1
输出样例#1:
3 3

说明

【注释】

比如有图

1 2 100

2 3 1

100个学生先冲到2号点,然后1个1个慢慢沿2-3边走过去

18神牛规定这样是不可以的……

也就是说,每批学生必须同时从起点出发,并且同时到达终点

  题目是比较裸的网络最大流吧,到今年汶川地震也刚好10年了,感慨一下。

  第一次交得了60分,以为是自己多虑判了重边(事实上也没有重边),改了过来50分(很懵);后来发现是前向星正反边互指并不能加减1啊。。。

  其实网络流模型是比较熟悉了,省选也考到了我当然没看出来这次是第一次用前向星写,也许是数据比较弱或者是增广路的回溯比较少,总之是第一次用前向星写网络流Ek。

  不用链表写原因一是不清楚各种考试环境的系统是否一样,64位下指针会吃亏,二是听说前向星寻找反边会比较方便(谁知道会毁在这里啊)

  大体就是广搜找增广路,找到了回溯,将所有增广路流量叠加就是最大流了,回溯时反向边原来使用一个*op指针指向反边的,前向星是可以用异或操作使得互为相反边的两条边在\(O(1)\)时间内互相调用的,这时cnt必须从0开始数,这样才会让两条相反边在二进制下只相差一位,因此边的循环边界就是-1了。

这个仇反正我是记下来了看来网络流的确是不仅要多看模板,还是要练基本功啊……

#include<cstdio>
#include<cstring>
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
struct node
{
    int n,v;
    int nxt;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=0;
    }
    node(){nxt=0;}
}e[4005];
int head[205],cnt=-1,sum=0;//cnt从-1开始循环
void add(int fr,int to,int v)
{
    e[++cnt]=node(to,v);
    e[cnt].nxt=head[fr];
    head[fr]=cnt;
}
int q[40005],l=0,r=0,n;
int pre[205];
bool used[205];
void pop(){q[l++]=0;}
void push(int x){q[++r]=x;}
void ek()
{
    int minn=0x7fffffff,p;
    while(1)
    {
        int flag=0;
        memset(used,0,sizeof(used));
        memset(pre,-1,sizeof(pre));//pre找边也要到-1终止
        minn=0x7fffffff;
        l=0,r=0;
        push(1);
        used[1]=true;
        while(l<r)
        {
            int k=q[l+1];
            pop();
            p=head[k];
            while(p!=-1)//同上
            {
                if(!used[e[p].n]&&e[p].v>0)
                {
                    used[e[p].n]=true;
                    pre[e[p].n]=p;
                    if(e[p].n==n)
                    {
                        flag=1;
                        break;
                    }
                    push(e[p].n);
                }
                p=e[p].nxt;
            }
            if(flag==1)
                break;
        }
        if(flag==0)
            return;
        p=pre[n];
        while(p!=-1)
        {
            minn=min(minn,e[p].v);
            p=pre[e[p^1].n];//这里是异或,001^010=011
        }
        p=pre[n];
        sum+=minn;
        while(p!=-1)
        {
            e[p].v-=minn;
            e[p^1].v+=minn;
            p=pre[e[p^1].n];
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    int m,s,u,v,w;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    ek();
    if(sum==0)
        puts("Orz Ni Jinan Saint Cow!");
    else
    {
        if(s==0)
            printf("%d 0\n",sum);
        else
            printf("%d %d\n",sum,(s-1)/sum+1);
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */