HDOJ 3416 Marriage Match IV【最短路+最大流】

bin神模板大法好

题意：从A到B，有多少条最短路径

搞法是：

先从A到B跑一遍最短路算法（以A为起点，B为终点，遍历全图）

再从B到A跑一遍最短路算法（以B为起点，A为终点，遍历全图）

然后，因为我们要求的是A到B的最短路径的条数，如果我们把图中不在A和B最短路径上的点和边全部删掉

就变成了求从A到B的流量问题，求的是最大流

我们在两遍最短路之后，判断每条边是不是在A到B的最短路径上

如果在，就添加到边集合中（准备跑最大流算法）

注意，这个题卡的时间比较高，SAP过不了

亲测，bin神的ISAP两种模板都能过

这种题目主要还是靠脑洞吧，然后就是靠模板

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

const int maxn=10500;
const int maxm=200010;
const int INF=0x3f3f3f3f;
struct Edge{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E1[maxn],E2[maxn];

void addedgeE1(int u,int v,int w){
    E1[u].push_back(Edge(v,w));
}

void addedgeE2(int u,int v,int w){
    E2[u].push_back(Edge(v,w));
}
bool vis[maxn];
int cnt[maxn],dist1[maxn],dist2[maxn];

bool SPFAE1(int Start,int n,int dist[]){
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++) dist[i]=INF;
    vis[Start]=true;
    dist[Start]=0;
    queue<int> que;
    while(!que.empty()) que.pop();
    que.push(Start);
    memset(cnt,0,sizeof(cnt));
    cnt[Start]=1;
    while(!que.empty()){
        int u=que.front();que.pop();
        vis[u]=false;
        for(int i=0;i<E1[u].size();i++){
            int v=E1[u][i].v;
            if (dist[v]>dist[u]+E1[u][i].cost){
                dist[v]=dist[u]+E1[u][i].cost;
                if (!vis[v]){
                    vis[v]=true;
                    que.push(v);
                    if (++cnt[v]>n) return false;
                }
            }
        }
    }
    return true;
}

bool SPFAE2(int Start,int n,int dist[]){
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++) dist[i]=INF;
    vis[Start]=true;
    dist[Start]=0;
    queue<int> que;
    while(!que.empty()) que.pop();
    que.push(Start);
    memset(cnt,0,sizeof(cnt));
    cnt[Start]=1;
    while(!que.empty()){
        int u=que.front();que.pop();
        vis[u]=false;
        for(int i=0;i<E2[u].size();i++){
            int v=E2[u][i].v;
            if (dist[v]>dist[u]+E2[u][i].cost){
                dist[v]=dist[u]+E2[u][i].cost;
                if (!vis[v]){
                    vis[v]=true;
                    que.push(v);
                    if (++cnt[v]>n) return false;
                }
            }
        }
    }
    return true;
}

struct Edge0{
    int to,nxt,cap,flow;
}edge[maxm];
int tol,head[maxn],gap[maxn],dep[maxn],cur[maxn];

int a[100050],b[100050],c[100050];

void init(){
    tol=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int w,int rw=0){
    edge[tol].to=v;
    edge[tol].cap=w;
    edge[tol].flow=0;
    edge[tol].nxt=head[u];
    head[u]=tol++;
    edge[tol].to=u;
    edge[tol].cap=rw;
    edge[tol].flow=0;
    edge[tol].nxt=head[v];
    head[v]=tol++;
}

int Q[maxn];
void BFS(int Start,int End){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]=1;
    int Front=0,Rear=0;
    dep[End]=0;
    Q[Rear++]=End;
    while(Front!=Rear){
        int u=Q[Front++];
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            if (dep[v]!=-1) continue;
            Q[Rear++]=v;
            dep[v]=dep[u]+1;
            gap[dep[v]]++;
        }
    }
}

int S[maxn];
int sap(int Start,int End,int N){
    BFS(Start,End);
    memcpy(cur,head,sizeof(head));
    int top=0;
    int u=Start;
    int ans=0;
    while(dep[Start]<N){
        if (u==End){
            int Min=INF;
            int inser;
            for(int i=0;i<top;i++)
            if (Min>edge[S[i]].cap-edge[S[i]].flow){
                Min=edge[S[i]].cap-edge[S[i]].flow;
                inser=i;
            }
            for(int i=0;i<top;i++){
                edge[S[i]].flow+=Min;
                edge[S[i]^1].flow-=Min;
            }
            ans+=Min;
            top=inser;
            u=edge[S[top]^1].to;
            continue;
        }
        bool flag=false;
        int v;
        for(int i=cur[u];i!=-1;i=edge[i].nxt){
            v=edge[i].to;
            if (edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){
                flag=true;
                cur[u]=i;
                break;
            }
        }
        if (flag){
            S[top++]=cur[u];
            u=v;
            continue;
        }
        int Min=N;
        for(int i=head[u];i!=-1;i=edge[i].nxt)
        if (edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){
            Min=dep[edge[i].to];
            cur[u]=i;
        }
        gap[dep[u]]--;
        if (!gap[dep[u]]) return ans;
        dep[u]=Min+1;
        gap[dep[u]]++;
        if (u!=Start) u=edge[S[--top]^1].to;
    }
    return ans;
}

int main(){
    //freopen("input.txt","r",stdin);
    int t,n,m,A,B;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++) E1[i].clear();
        for(int i=0;i<=n;i++) E2[i].clear();
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
            addedgeE1(a[i],b[i],c[i]);
            addedgeE2(b[i],a[i],c[i]);
        }
        scanf("%d%d",&A,&B);
        SPFAE1(A,n,dist1);
        SPFAE2(B,n,dist2);
        init();
        for(int i=1;i<=m;i++)
            if (dist1[a[i]]+dist2[b[i]]+c[i]==dist2[A])
                addedge(a[i],b[i],1);
        printf("%d\n",sap(A,B,n));
    }
    return 0;
}