洛谷 P10P1343 地震逃生 改错

P1343 地震逃生

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

---

很明显网络流的裸题。

前几天看到对前向星用\(x\) \(nor\) 1\(找反边，觉得很方便，遂用一下，用想到很久没打\)dinic$了，就决定打打(以前都是偷懒打EK的)

不过这样找反边\(head\)最开始时得赋\(-1\)，而且边的边界也是-1

因为

\(x\) \(nor\) \(1=x+1\)，\(x\)为偶

\(x\) \(nor\) \(1=x-1\)，\(x\)为奇

得用上0

然后我.....

我是得多智障才这样,居然样例还对了...

还有一点，最后算答案是\((ans-1)/\)最大流\(+1\)

我没给那个\(ans\)减一下

---

code：

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

const int N=204;

const int M=2004;

const int inf=0x3f3f3f3f;

struct Edge

{

    int w,to,next;

}edge[M*2];

struct node

{

    int cnt,u;

}S[N];

int n,m,X,cnt=-1,head[N];

int top=0;

void push(int cnt0,int u0) {S[++top].cnt=cnt0,S[top].u=u0;}

void pop() {top--;}

int read()

{

    int x=0;char c=getchar();

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}

    return x;

}

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

{

    edge[++cnt].next=head[u],edge[cnt].to=v,edge[cnt].w=w,head[u]=cnt;

    edge[++cnt].next=head[v],edge[cnt].to=u,edge[cnt].w=0,head[v]=cnt;

}

int dep[N],used[N],ans=0;

queue <int > q;

bool bfs()

{

    memset(dep,0,sizeof(dep));

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

    q.push(1);dep[1]=1;

    while(!q.empty()&&q.front()!=n)

    {

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=edge[i].next)

        {

            int v=edge[i].to,w=edge[i].w;

            if(!dep[v]&&w)

            {

                dep[v]=dep[u]+1;

                q.push(v);

            }

        }

    }

    return !q.empty();

}

int main()

{

    memset(head,-1,sizeof(head));

    n=read(),m=read(),X=read();

    int u,v,w;

    for(int i=1;i<=m;i++)

    {

        u=read(),v=read(),w=read();

        add(u,v,w);

    }

    while(bfs())

    {

        memset(used,0,sizeof(used));

        top=0;

        push(head[1],1);

        while(top)

        {

            if(S[top].u==n)

            {

                int m_min=inf,id;

                for(int i=2;i<=top;i++)

                    if(edge[S[i].cnt].w<m_min)

                    {

                        m_min=edge[S[i].cnt].w;

                        id=i;

                    }

                ans+=m_min;

                for(int i=2;i<=top;i++)

                {

                    edge[S[i].cnt].w-=m_min;

                    edge[(S[i].cnt)^1].w+=m_min;

                }

                used[n]=0;

                top=max(0,id-1);

            }

            else

            {

                int u=S[top].u;

                for(int i=head[u];i!=-1;i=edge[i].next)

                {

                    int v=edge[i].to,w=edge[i].w;

                    if(!used[v]&&w&&dep[v]==dep[u]+1)

                    {

                        used[v]=1;

                        push(i,v);

                        break;

                    }

                }

                if(S[top].u==u) top--;

            }

        }

    }

    if(ans==0) {printf("Orz Ni Jinan Saint Cow!\n");return 0;}

    printf("%d %d\n",ans,(X-1)/ans+1);

    return 0;

}

---

2018.5.20