如题,Dinic 过了,HLPP WA on #7。

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,h[33],cnt=-1,ht[33],gap[32],mh,hp;
struct edge{int nxt,id,d;}e[2000];
void add_path(int u,int v,int w)
{
    e[++cnt]=edge{h[u],v,w};
    h[u]=cnt;
}
long long ex[33];
queue<int>b[32],q;
bool push(int u)
{
    bool init=u==s;
    for(int i=h[u];~i;i=e[i].nxt)
    {
        int&v=e[i].id,&w=e[i].d;
        if(!w||!init&&ht[u]!=ht[v]+1||ht[v]==n+2)continue;
        long long k=init?w:min(1ll*w,ex[u]);
        if(v!=s&&v!=t&&!ex[v])
        {
            b[ht[v]].push(v);
            mh=max(mh,ht[v]);
        }
        ex[u]-=k;
        ex[v]+=k;
        w-=k;
        e[i^1].d+=k;
        if(!ex[u])return 0;
    }
    return 1;
}
void relabel(int u)
{
    ht[u]=n+2;
    for(int i=h[u];i;i=e[i].nxt)if(e[i].d)ht[u]=min(ht[u],ht[e[i].id]);
    if(++ht[u]<n)
    {
        b[ht[u]].push(u);
        mh=max(mh,ht[u]);
        ++gap[ht[u]];
    }
}
bool bfs()
{
    for(int i=1;i<=n;i++)ht[i]=n+2;
    q.push(t);
    ht[t]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];~i;i=e[i].nxt)
        {
            int&v=e[i].id;
            if(e[i^1].d&&ht[v]>ht[u]+1)
            {
                ht[v]=ht[u]+1;
                q.push(v);
            }
        }
    }
    return ht[s]!=n+2;
}
int select()
{
    while(!b[mh].size()&&mh>-1)--mh;
    return mh>-1?b[mh].front():0;
}
long long HLPP()
{
    if(!bfs())return 0;
    for(int i=1;i<=n;i++)if(ht[i]!=n+2)++gap[ht[i]];
    ht[s]=n;
    push(s);
    while(hp=select())
    {
        b[mh].pop();
        if(push(hp))
        {
            if(!--gap[ht[hp]])for(int i=1;i<=n;i++)if(i!=s&&ht[i]>ht[hp]&&ht[i]<n+1)ht[i]=n+1;
            relabel(hp);
        }
    }
    return ex[t];
}
signed main()
{
    scanf("%d%d",&n,&m);
    s=1;t=n;
    for(int i=1;i<=n;i++)h[i]=-1;
    for(int i=1,x,y,z;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add_path(x,y,z);
        add_path(y,x,0);
    }
    printf("%lld ",HLPP());
    for(int i=0;i<(m<<1);i++)
    {
        if(i&1)e[i].d=0;
        else
        {
            if(!e[i].d)e[i].d=1;
            else e[i].d=2000001;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ex[i]=0;
        while(!b[i].empty())b[i].pop();
    }
    printf("%lld\n",HLPP());
    return 0;
}