HDU - 6582 Path

传送门：HDU - 6582

思路分析

删掉一些边，使得$1$到$n$的最短路变长
很明显的最小割问题，可能删除的边一定是最短路上经过的边
那么怎么判断哪些边是最短路上的呢，连反向边
令$d1$为1到各个点的距离，$d2$为$n$到各个点的距离
比如一条边$u–v$边权为$w$
如果这条边是最短路上的边，那么一定满足$d1[u]+d2[v]+w==d1[n]$
将满足条件的点全部连边跑一遍最小割就行了

样例输入

1
3 4
1 2 1
2 3 1
1 3 2
1 3 3

样例输出

3

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long

using namespace std;

const int INF = 1e18;
const int N=1e5+10;

vector<pair<int,int>>e1[N],e2[N];

struct node {
    int v,w,next;
} e[N];


int cnt=1,head[N<<1],d1[N],d2[N],dep[N],vis[N];
int n,m;

void add(int u,int v,int w) {
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void dij(int s,int *dis,vector<pair<int,int>> *edge) {
    for(int i=0;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
    }
    dis[s]=0;
    priority_queue<pair<int,int> > q;
    q.push(make_pair(-dis[s],s));
    while(!q.empty()) {
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i:edge[u]) {
            int v=i.fi;
            int w=i.se;
            if(!vis[v]&&dis[v]>dis[u]+w) {
                dis[v]=dis[u]+w;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
}

bool bfs(int s,int t) {
    queue<int>q;
    mem(dep,0); 
    dep[s]=1;  
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u]; i ; i=e[i].next) {
            int v=e[i].v;
            int w=e[i].w;
            if(w && !dep[v]) { 
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }

    return dep[t];
}

int dfs(int u,int f,int t) {
    int fl=0;
    if(u==t)
        return f;
    for(int i=head[u]; i && f ; i=e[i].next) {
        int v=e[i].v;
        if(dep[v]==dep[u]+1 && e[i].w) { 
            int nx=dfs(v,min(f,e[i].w),t);
            e[i].w-=nx;
            e[i^1].w+=nx;
            f-=nx;
            fl+=nx;
        }
    }
    if(!fl)
        dep[u]=-2;
    return fl;

}

int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t))
        ans+=dfs(s,INF,t); 
    return ans;
}



signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    scanf("%lld",&t);
    while(t--) {
        cnt=1;
        mem(head,0);
        scanf("%lld%lld",&n,&m);
        while(m--) {
            int u,v,w;
            scanf("%lld%lld%lld",&u,&v,&w);
            e1[u].push_back(mp(v,w));
            e2[v].push_back(mp(u,w));

        }
        dij(1,d1,e1);
        dij(n,d2,e2);
        if(d1[n]==INF) {
            puts("0");
            continue;
        }
        for(int u=1; u<=n; u++) {
            for(auto i:e1[u]) {
                int v=i.fi;
                int w=i.se;
                if(d1[u]+d2[v]+w==d1[n]) {
                    add(u,v,w);
                    add(v,u,0);
                }
            }
        }
        printf("%lld\n",dinic(1,n));
        for(int i=1;i<=n;i++){
            e1[i].clear();
            e2[i].clear();
        }

    }




    return 0;
}