P1343 地震逃生「最大流」

地震逃生

题意：

• 每条边有最大容量。但是有多条边。求出数量需要多少批才能运送完成

思路：

• 最大流

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M=40010;
int n,m,x,cnt=0;
int head[M];
int dis[M];
int cur[M];
struct node
{
    int v,w,nxt;
} edge[M];
void add(int x,int y,int w)
{
    edge[cnt].v=y;
    edge[cnt].w=w;
    edge[cnt].nxt=head[x];
    head[x]=cnt++;
}
void dataset( )
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&n,&m,&x);
    int a,b,c;
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,0);
    }
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[1]=0;
    queue<int>qu;
    qu.push(1);
    while(!qu.empty( ))
    {
        int u=qu.front( );
        qu.pop( );
        for(int i=head[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            if(dis[v]==-1&&edge[i].w)
            {
                dis[v]=dis[u]+1;
                qu.push(v);
            }
        }
    }
    return dis[n]!=-1;
}
int dfs(int u,int flo)
{
    if(u==n)
    {
        return flo;
    }
    int detla=flo;
    for(int i=cur[u]; i!=-1; i=edge[i].nxt)
    {
        cur[u]=edge[i].nxt;
        int v=edge[i].v;
        if(dis[v]==dis[u]+1&&edge[i].w>0)
        {
            int d=dfs(v,min(detla,edge[i].w));
            edge[i].w-=d;
            edge[i^1].w+=d;
            detla-=d;
            if(detla==0)
            {
                break;
            }
        }

    }
    // for(int i=head[u];i!=-1;i=edge[i].nxt)
    // {
    //     int v=edge[i].v;
    //     if(dis[v]==dis[u]+1&&edge[i].w>0)
    //     {
    //         int d=dfs(v,min(detla,edge[i].w));
    //         edge[i].w-=d;
    //         edge[i^1].w+=d;
    //         detla-=d;
    //         if(detla==0)
    //         {
    //             break;
    //         }
    //     }
    // }
    return flo-detla;
}
int dini( )
{
    int ans=0;
    while(bfs( ))
    {
        for(int i=1; i<=n; i++)
        {
            cur[i]=head[i];
        }
        ans+=dfs(1,INF);
    }
    return ans;
}
int main( )
{
    dataset( );
    int a=dini( );
    if(a!=0)
    {
        if(x%a)
        {
            printf("%d %d\n",a,x/a+1);
        }
        else
        {
            printf("%d %d\n",a,x/a);
        }
    }
    else
    {
        printf("Orz Ni Jinan Saint Cow!\n");
    }
    return 0;

}