题解 P1343 【地震逃生】

attack · 2017-07-10 15:34:43 · 题解

来一发Dinic。

这题比较少，我们想一下，如果要输送学生，我们只要找出每次可以通过的最大的学生数量就好。

然后用一点贪心的原理，每次都去用最大的输送方案输送学生（废话。。）

只要最大流不为0就一定能输送完成

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define lli long long int 
using namespace std;
const int MAXN=300001;
const int maxn=0x7fffff;
void read(int &n)
{
    char c='+';int x=0;bool flag=0;
    while(c<'0'||c>'9')
    {c=getchar();if(c=='-')flag=1;}
    while(c>='0'&&c<='9')
    {x=(x<<1)+(x<<3)+c-48;c=getchar();}
    flag==1?n=-x:n=x;
}
struct node
{
    int u,v,flow,cap,nxt;
}edge[MAXN];
int head[MAXN];
int num=0;
int n,m,S,T,x;
int dis[MAXN];
int vis[MAXN];
int cur[MAXN];
void add_edge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].cap=z;
    edge[num].flow=0;
    edge[num].nxt=head[x];
    head[x]=num++;
}
bool bfs(int bg,int ed)
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    q.push(bg);
    dis[bg]=0;
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        for(int i=head[p];i!=-1;i=edge[i].nxt)
        {
            if(dis[edge[i].v]==-1&&edge[i].cap>edge[i].flow)
            {
                vis[edge[i].v]=1;
                dis[edge[i].v]=dis[edge[i].u]+1;
                  q.push(edge[i].v);            
            }
        }
    }
    if(dis[ed]==-1)
        return 0;
    else return 1;
}
int dfs(int now,int a)// a:所有弧的最小残量 
{
    if(now==T||a<=0)
        return a;
    int flow=0,f;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(dis[now]+1==dis[edge[i].v]&&edge[i].cap-edge[i].flow>0)
        {
            f=dfs(edge[i].v,min(a,edge[i].cap-edge[i].flow));
            edge[i].flow+=f;
            edge[i^1].flow-=f;
            flow+=f;
            a-=f;
            if(a<=0)break;
        }
    }
    return flow;
}
void Dinic(int S,int T)
{
    int ansflow=0;
    int cs=0;
    int maxflow=0;
    for(int i=1;i<=n;i++)
            cur[i]=head[i];
    while(bfs(S,T))
    {
        int p=dfs(S,maxn);
        cs++;
        ansflow+=p;
        maxflow=max(maxflow,p); 
    }// 求出层级
    if(ansflow==0)
        printf("Orz Ni Jinan Saint Cow!");
    else 
        printf("%d %d",ansflow,(x%ansflow)==0?(x/ansflow):(x/ansflow+1));
    //printf("%d",ansflow);
}
int main()
{
    scanf("%d%d%d",&n,&m,&x);
    //read(n);read(m);read(x);
//    swap(n,m);
    S=1;T=n;
   // read(S);read(T);
    for(int i=1;i<=n;i++)
        head[i]=-1;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        //read(x);read(y);read(z);
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
        add_edge(y,x,0);
    }
    Dinic(S,T);
    return 0;
}