题解 P1343 【地震逃生】

芬特 · 2017-05-06 20:22:59 · 题解

看了看好像没用isap算法，我就来一个

数据好像很小，isap跑得飞快，只有一个点比较坑，t了一次

主要是maxflow除出来再取整，然后不要写错板子就可以啦

代码如下

#include<bits/stdc++.h>
#define min(x,y) (x<y?x:y)
#define maxn 10005
#define inf 1<<30
using namespace std;
struct edge{
    int from,to,cap,flow;
};
struct isap
{
    int s,t,n,p[maxn],d[maxn],num[maxn],cur[maxn];
    bool vis[maxn];
    vector<edge>edges;
    vector<int>g[maxn];
    void init(int s,int t,int n)
    {
        this->s=s;
        this->t=t;
        this->n=n;
        for(int i=1;i<=n;i++)
        g[i].clear();
        edges.clear();
    }
    void addedge(int from,int to,int cap)
    {
        edges.push_back((edge){from,to,cap,0});
        edges.push_back((edge){to,from,0,0});
        int m=edges.size();
        g[from].push_back(m-2);
        g[to].push_back(m-1);
    }
    void bfs()
    {
    queue<int>q;
    q.push(t);
    vis[t]=1,d[t]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=0;i<g[x].size();i++)
        {
            edge& e=edges[g[x][i]^1];
            if(!vis[e.from]&&e.flow<e.cap)
            {
                vis[e.from]=1;
                d[e.from]=d[x]+1;
                q.push(e.from);
            }
        }
    }
    }
    int augment()
    {
        int x=t,a=inf;
        while(x!=s)
        {
            edge& e=edges[p[x]];
            a=min(a,e.cap-e.flow);
            x=e.from;
        }
        x=t;
        while(x!=s)
        {
            edge&e=edges[p[x]];
            e.flow+=a;
            edges[p[x]^1].flow=-a;
            x=e.from;
        }
        return a;
    }
    int maxflow()
    {
        int flow=0;
        bfs();
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++) num[d[i]]++;
        memset(cur,0,sizeof(cur));
        int x=s;
        while(d[s]<n)
        {
            if(x==t)
            {
                flow+=augment();
                x=s;
            }
            bool ok=0;
            for(int i=cur[x];i<g[x].size();i++)
            {
                edge& e=edges[g[x][i]];
                if (d[x]==d[e.to]+1 && e.cap>e.flow)
                {
                    p[e.to]=g[x][i];
                    cur[x]=i; x=e.to;
                    ok=1;
                    break;
                }
            }
            if(!ok)
            {
            int m=n-1;
            for(int i=0;i<g[x].size();i++)
            {
                edge& e=edges[g[x][i]];
                if(e.cap>e.flow) m=min(m,d[e.to]);
            }
            num[d[x]]--;
            if(!num[d[x]]) break;
            d[x]=m+1;num[d[x]]++;
            cur[x]=0;
            if(x!=s)x=edges[p[x]].from;
            }
        }
        return flow;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    int n,m,s,t,u,v,w,X;
    cin>>n>>m>>X;
    s=1,t=n;
    isap get_sap;
    get_sap.init(s,t,n);
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        get_sap.addedge(u,v,w);
    }
    int max_flow=get_sap.maxflow();    
    if(max_flow>0)
    {
    int ans=X/max_flow;
    cout<<max_flow<<" ";
    if(ans*max_flow==X) cout<<ans;
    else cout<<ans+1;
    }
    else 
    {
        cout<<"Orz Ni Jinan Saint Cow!";
    }
    return 0;
}