hdu 6582 19 航电多校第一场1005题 path 【最短路+最小割】

题目链接：

/*
思路：最短路径构成的图的最小割（即最大流）
最短路径图：spaf得到 1 到所有点的单源最短路（dis），再求出 n 到所有点的单源最短路（dis1）
遍历每条路，设当前边起点为 u ，终点为 v ，圈主为 w ， 如果 dis[u]+dis1[v]+w==1到n的最短路径
那么就是最短路径图的边
然后网络流最小割（最大流）跑一遍就能得出答案
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;///这里注意  inf要够大，找了半年的bug
const int N=3e4;

struct node
{
    ll ne,v,w,u;
    node(ll _ne=0,ll _v=0,ll _w=0,ll _u=0):ne(_ne),v(_v),w(_w),u(_u){}
}q[N],q1[N],edge[N];
ll f[N],vis[N],dis[N],f1[N],dis1[N];
ll cur[N];
ll n,m,e,top;

void spaf()///最短路算法，得到起点为1的单源最短路
{
    queue<ll>que;
    que.push(1);
    for(ll i=1;i<=n;i++)
    {
        dis[i]=inf;
        vis[i]=0;
    }
    vis[1]=1;
    dis[1]=0;
    while(!que.empty())
    {
        ll u=que.front();
        que.pop();
        vis[u]=0;
        for(ll i=f[u];i!=-1;i=q[i].ne)
        {
            ll v=q[i].v,w=q[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(vis[v]==0)
                {
                    vis[v]=1;
                    que.push(v);
                }
            }
        }
    }
}

void spaf1()///得到起点为n的单源最短路
{
    queue<ll>que;
    que.push(n);
    for(ll i=1;i<=n;i++)
    {
        dis1[i]=inf;
        vis[i]=0;
    }
    vis[n]=1;
    dis1[n]=0;
    while(!que.empty())
    {
        ll u=que.front();
        que.pop();
        vis[u]=0;
        for(ll i=f1[u];i!=-1;i=q1[i].ne)
        {
            ll v=q1[i].v,w=q1[i].w;
            if(dis1[v]>dis1[u]+w)
            {
                dis1[v]=dis1[u]+w;
                if(vis[v]==0)
                {
                    vis[v]=1;
                    que.push(v);
                }
            }
        }
    }
}

ll dinic_dfs(ll now,ll maxx)
{
    if(now==n) return maxx;
    ll ret=0;
    for(ll &i=cur[now];i!=-1;i=edge[i].ne)
    {
        ll v=edge[i].v,w=edge[i].w;
        if(w&&dis[v]==dis[now]+1)
        {
            ll mini=min(w,maxx-ret);
            w=dinic_dfs(v,mini);
            edge[i].w-=w;
            edge[i^1].w+=w;
            ret+=w;
            if(ret==maxx) return ret;
        }
    }
    return ret;
}

ll dinic_bfs()
{
    memset(dis,0,sizeof(dis));
    dis[1]=1;
    queue<ll>que;
    que.push(1);
    while(!que.empty())
    {
        ll u=que.front();
        que.pop();
        if(u==n) return 1;
        for(ll i=f[u];i!=-1;i=edge[i].ne)
        {
            ll v=edge[i].v,w=edge[i].w;
            if(!dis[v]&&w)
            {
                dis[v]=dis[u]+1;
                que.push(v);
            }
        }
    }
    return 0;
}

ll dinic()///网络流模板
{
    ll ans=0;
    while(dinic_bfs())
    {
        for(ll i=1;i<=n;i++)
            cur[i]=f[i];
        ans+=dinic_dfs(1,inf);
    }
    return ans;
}

int main()
{
//    freopen("E:\\02.txt","r",stdin);
    ll T;
    scanf("%lld",&T);
    while(T--)
    {
        ll a,b,c;
        scanf("%lld %lld",&n,&m);
        memset(f,-1,sizeof(f));
        memset(f1,-1,sizeof(f1));
        top=0;e=0;
        for(ll i=1;i<=m;i++)
        {
            scanf("%lld %lld %lld",&a,&b,&c);
            q[e]=node(f[a],b,c,a);
            f[a]=e;
            q1[e]=node(f1[b],a,c,b);
            f1[b]=e++;
        }
        spaf();
        if(dis[n]==inf)
        {
            printf("0\n");
            continue;
        }
        spaf1();
        ll min_path=dis1[1];
        memset(f,-1,sizeof(f));
        for(ll i=0;i<e;i++)
        {
            ll u=q[i].u,v=q[i].v;
            if(dis[u]+dis1[v]+q[i].w==min_path)
            {
                edge[top]=node(f[u],v,q[i].w,u);
                f[u]=top++;
                edge[top]=node(f[v],u,0,v);
                f[v]=top++;
            }
        }
        printf("%lld\n",dinic());
    }
    return 0;
}