题解 P4845 【LJJ爱数树】

Habib · 2018-10-27 22:37:43 · 题解

include<bits/stdc++.h>

#define il inline
#define ll long long 
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
const ll N=100005,inf=233333333333333,mod=2018;
ll n,m,s,t,h[100],dis[2005],cnt=1;
ll ans;
struct edge{
ll to,net;ll v;
}e[N];
il void add(ll u,ll v,ll w)
{
    e[++cnt].to=v,e[cnt].net=h[u],e[cnt].v=w,h[u]=cnt;
    e[++cnt].to=u,e[cnt].net=h[v],e[cnt].v=0,h[v]=cnt;
}
queue<ll>q;
il bool bfs()
{
    memset(dis,-1,sizeof(dis));
    q.push(s),dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].net)
        if(dis[e[i].to]==-1&&e[i].v>0)dis[e[i].to]=dis[u]+1,q.push(e[i].to);
    }
    return dis[t]!=-1;
}
il ll dfs(ll u,ll op)
{
    if(u==t)return op;
    ll flow=0,used=0;
    for(int i=h[u];i;i=e[i].net)
    {
        int v=e[i].to;
        if(dis[v]==dis[u]+1&&e[i].v>0)
        {
            used=dfs(v,min(op,e[i].v));
            if(!used)continue;
            flow+=used,op-=used;
            e[i].v-=used,e[i^1].v+=used;
            if(!op)break;
        }
    }
    if(!flow)dis[u]=-1;
    return flow;
}
int main()
{
    scanf("%lld%lld",&n,&m);s=1,t=n;
    ll u,v;ll w;
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w*mod+1);
    }
    while(bfs())ans+=dfs(s,inf);
    printf("%lld %lld\n",ans/mod,ans%mod);
    return 0;

}