HDU4725(Marriage Match IV)

链接：https://vjudge.net/problem/HDU-3416
思路：求最短路一共多少条，首先想清楚一点，如果某条路是最短路，那他路上所有点的距离都应该是最短路的距离，为了求出所有最短路存在的边，我们枚举所有边，如果两个端点的最短距离差等于边长， 那么这条边就一定会被选入最短路，然后在网络流上建一条容量为1的边，最后跑一个最大流即可
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1010;
const int INF = 1e9;
typedef pair<int,int> P;

struct edge1{
    int from,to,dist;
};

struct edge{
    int from,to,cap,flow;
};

struct Dij{
    int n,m;
    int d[2][maxn];
    vector<int> G[2][maxn];
    vector<edge1> edges[2];

    void init(int n){
        this->n = n;
        for(int i=0;i<=n;i++)G[0][i].clear(),G[1][i].clear();
        edges[0].clear();
        edges[1].clear();
    }

    void addedge(int from,int to,int dist,int f){
        edges[f].push_back(edge1{from,to,dist});
        m = edges[f].size();
        G[f][from].push_back(m-1);
    }

    void dij(int s,int f){
        for(int i=0;i<=n;i++)d[f][i] = 1e9;
        d[f][s] = 0;
        priority_queue<P,vector<P>,greater<P> >q;
        q.push(P{0,s});
        d[f][s] = 0;
        while(!q.empty()){
            P p = q.top();
            q.pop();
            int u = p.second;
            if(d[f][u]<p.first)continue;
            for(int i=0;i<G[f][u].size();i++){
                edge1 &e = edges[f][G[f][u][i]];
                if(d[f][e.to]>d[f][u]+e.dist){
                    d[f][e.to] = d[f][u] + e.dist;
                    q.push(P{d[f][e.to],e.to});
                }
            }
        }
    }
}solver1;

struct Dinic{
    int n,m,s,t;
    vector<edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n){
        this->n = n;
        edges.clear();
        for(int i=0;i<=n;i++)G[i].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});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool bfs(){
        memset(vis,0,sizeof(vis));
        queue<int> q;
        q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while(!q.empty()){
            int x = q.front();
            q.pop();
            for(int i=0;i<G[x].size();i++){
                edge &e = edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int a){
        if(x==t||a==0)return a;
        int flow = 0,f;
        for(int &i = cur[x];i<G[x].size();i++){
            edge &e = edges[G[x][i]];
            if(d[x] + 1 == d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[G[x][i]^1].flow -=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }

    int maxflow(int s,int t){
        this->s = s;
        this->t = t;
        int flow = 0;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            flow+=dfs(s,INF);
        }
        return flow;
    }
}solver2;

int T;
int n,m;
int s,t;

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        solver1.init(n);
        solver2.init(n);
        for(int i=0;i<m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            solver1.addedge(a,b,c,0);
            solver1.addedge(b,a,c,1);
        }
        scanf("%d%d",&s,&t);
        solver1.dij(s,0);
        solver1.dij(t,1);
        int res = solver1.d[0][t];
        for(int i=0;i<solver1.edges[0].size();i++){
            int u = solver1.edges[0][i].from;
            int v = solver1.edges[0][i].to;
            int w = solver1.edges[0][i].dist;
            if(solver1.d[0][u]+solver1.d[1][v]+w==res)solver2.addedge(u,v,1);
        }
        int ans = solver2.maxflow(s,t);
        printf("%d\n",ans);
    }
    return 0;
}