HDU3416 网络流+最短路

HDU3416 Marriage Match IV

给一个带权有向图，两个点AB，求A到B有几条最短路，每条边只能走以次！
先跑两边Dij，求出A到各个点的最短路和各个点到B的最短路，后者是先反向建边在跑Dij就行，然后枚举边，若满足dist1[from]+e[i].weight+dist[to] == dist1[B]，则说明所有的最短路中包含此条边，找到所有的这样的边，然后在这些边上跑网络流，每条边的流量设置为1，最后跑出来的结果就是答案。

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1005, maxm = 1e5+5;
struct node{
    int pos, dist;
    node(int a, int b): pos(a), dist(b){}
    friend bool operator < (const struct node &a, const struct node &b){
        return a.dist > b.dist;
    }
};
struct edge{
    int from, to, dist, next;
}e[maxm*2];
int n, m, tot, A, B;
int head[maxn], vis[maxn], dist1[maxn], dist2[maxn];

struct Edge{
    int from, to, c, f;
    Edge(int a, int b, int e, int d): from(a), to(b), c(e), f(d){}
};

int cnt, depth[maxn], cur[maxn];
vector<Edge> E;
vector<int> G[maxn];

inline bool BFS(int s, int t){
    for (int i=1; i<=n; i++)    depth[i] = 0;
    depth[s] = 1;
    queue<int> q;
    q.push(s);
    while (!q.empty()){
        int tmp = q.front();    q.pop();
        for (int i=0; i<G[tmp].size(); i++){
            Edge& e = E[G[tmp][i]];
            if (e.c>e.f && !depth[e.to]){
                depth[e.to] = depth[tmp] + 1;
                q.push(e.to);
            }
        }
    }
    return depth[t];
}

inline int DFS(int s, int t, int flow){
    if (s==t || flow<=0)    return flow;
    int rest = flow;
    for (int &i=cur[s]; i<G[s].size(); i++)  if (depth[E[G[s][i]].to]==depth[s]+1 && E[G[s][i]].c>E[G[s][i]].f){
        int tmp = DFS(E[G[s][i]].to, t, min(rest, E[G[s][i]].c-E[G[s][i]].f));
        if (tmp<=0) depth[E[G[s][i]].to] = 0;
        rest -= tmp;
        E[G[s][i]].f += tmp;
        E[G[s][i]^1].f -= tmp;
        if (rest==0)    break;
    }
    return flow - rest;
}

int DINIC(int s, int t){
    int ans = 0;
    while (BFS(s, t)){
        ans += DFS(s, t, 9999999);
        for (int i=1; i<=n; i++)    cur[i] = 0;
    }
    return ans;
}

inline void Add(int from, int to, int cap){
    E.push_back(Edge(from, to, cap, 0));
    E.push_back(Edge(to, from, 0, 0));
    cnt += 2;
    G[from].push_back(cnt-2);
    G[to].push_back(cnt-1);
    return;
}

void Dijkstra(int s, int dist[]){
    for (int i=1; i<=n; i++)    vis[i] = 0, dist[i] = 999999999;
    priority_queue<node> q;
    dist[s] = 0;
    q.push(node(s, 0));
    while (!q.empty()){
        node tmp = q.top();    q.pop();
        if (vis[tmp.pos])   continue;
        vis[tmp.pos] = 1;
        for (int i=head[tmp.pos]; i; i=e[i].next)   if (dist[e[i].to] > tmp.dist+e[i].dist){
            dist[e[i].to] = tmp.dist+e[i].dist;
            q.push(node(e[i].to, dist[e[i].to]));
        }
    }
    return;
}

inline void add(int from, int to, int dist){
    tot++;
    e[tot].from = from, e[tot].to = to, e[tot].dist = dist, e[tot].next = head[from];
    head[from] = tot;
    return;
}
inline int read(){
    int x=0;    char ch=getchar();
    while (ch<'0' || ch>'9')    ch=getchar();
    while (ch>='0' && ch<='9'){
        x = x*10 + ch-'0';
        ch=getchar();
    }
    return x;
}

int main(){
    int t = read(), from, to, w;
    while (t--){
        n = read(), m = read(), tot = cnt = 0;
        for (int i=1; i<=n; i++)    head[i] = 0;
        E.clear();
        for (int i=1; i<=n; i++)    G[i].clear();
        for (int i=1; i<=m; i++){
            from = read(), to = read(), w = read();
            add(from, to, w);
        }
        A = read(), B = read();
        Dijkstra(A, dist1);
        for (int j=1; j<=2; j++){
            for (int i=1; i<=n; i++)    head[i] = 0;
            for (int i=1; i<=tot; i++){
                int tmp = e[i].from;
                e[i].from = e[i].to;
                e[i].to = tmp;
                e[i].next = head[e[i].from];
                head[e[i].from] = i;
            }
            if (j==1)   Dijkstra(B, dist2);
        }
        for (int i=1; i<=tot; i++)  if (dist1[e[i].from]+e[i].dist+dist2[e[i].to] == dist1[B]){
            Add(e[i].from, e[i].to, 1);
        }
        printf ("%d\n", DINIC(A, B));
    }
    return 0;
}