最短路+最大流

刚开始没有理解题意，总感觉求一个最大流不就行了吗？
原来真正的题意是，最短路始终不变的。我们每一次必须从最短路走。

正确的做法是，我们正反方向求一次最短路。
然后，枚举边。如果边<u,v> d[1->u]+e.cost+d[v->n] == mincost
那么我们就给这条边一个cap==1
ok
然后求一个最大流就可以了。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
typedef pair<int,int> pii;
const int max_n = 1200;
const int max_m = 1e5+100;
const int inf = 1e9;
struct edge{
    int to,cost,cap,next;
}E[max_m<<2];
int head[max_n];
int cnt = 0;
void add(int from,int to,int cost){
    E[cnt].to = to;
    E[cnt].cost = cost;
    E[cnt].next=head[from];
    head[from]=cnt++;
}

int n,m;
int es[max_m][3];
int dd[3][max_n];
int dist;
int gap[max_n],last[max_n],d[max_n],que[max_n],ql,qr;
void add2(int u,int to,int cap) {
    E[++cnt].to=to;E[cnt].cap=cap;
    E[cnt].next=head[u];head[u]=cnt;
    E[++cnt].to=u;E[cnt].cap=0;
    E[cnt].next=head[to];head[to]=cnt;
}int aug(int x,int s,int t,int mi) {
    if (x==t) return mi;
    int flow=0;
    for (int &i=last[x],v=E[i].to;i;i=E[i].next,v=E[i].to) if (d[x]==d[v]+1) {
        int tmp=aug(v,s,t,min(mi,E[i].cap));
        flow+=tmp,mi-=tmp,E[i].cap-=tmp,E[i^1].cap+=tmp;
        if (!mi) return flow;
    }
    if (!(--gap[d[x]])) d[s]=n+1;
    ++gap[++d[x]],last[x]=head[x];
    return flow;
}
int maxflow(int s,int t) {
    fill(gap,gap+n+10,0);fill(d,d+n+10,0);
    ++gap[d[t]=1];
    for (int i=1;i<=n;++i) last[i]=head[i];
    que[ql=qr=1]=t;
    while (ql<=qr) {
        int x=que[ql++];
        for (int i=head[x],v=E[i].to;i;i=E[i].next,v=E[i].to) if (!d[v]) ++gap[d[v]=d[x]+1],que[++qr]=v;
    }

    int ret=aug(s,s,t,inf);
    while (d[s]<=n)    ret+=aug(s,s,t,inf);
    return ret;
}

int dijstra(int s,int t,int id){
    priority_queue<pii,vector<pii>,greater<pii>> que;
    for (int i=0;i<=n;++i)dd[id][i]=inf;
    dd[id][s]=0;que.push(pii(dd[id][s],s));
    while (!que.empty()){
        pii p = que.top();que.pop();
        int u = p.second;int dt = p.first;
        if (dt>dd[id][u])continue;
        for (int i=head[u];i;i=E[i].next){
            int v = E[i].to;
            if (dd[id][v]>E[i].cost+dt){
                dd[id][v]=E[i].cost+dt;
                que.push(pii(dd[id][v],v));
            }
        }
    }return dd[id][t];
}

int main(){
    int T;scanf("%d",&T);
    while (T--){
        dist = inf;
        scanf("%d %d",&n,&m);
        fill(head,head+n+10,0);cnt=1;
        for (int i=1;i<=m;++i){
            scanf("%d %d %d",&es[i][0],&es[i][1],&es[i][2]);
            add(es[i][0],es[i][1],es[i][2]);
        }
        int A,B;cin>>A>>B;
        dist = dijstra(A,B,1);
        fill(head,head+n+10,0);cnt=1;
        for (int i=1;i<=m;++i){
            add(es[i][1],es[i][0],es[i][2]);
        }dijstra(B,A,2);
        fill(head,head+n+10,0);cnt=1;
        for (int i=1;i<=m;++i){
            int from = es[i][0];
            int to = es[i][1];
            int cost = es[i][2];
            if (dd[1][from]+dd[2][to]+cost==dist)
                add2(from,to,1);
        }
        cout<<maxflow(A,B)<<endl;
    }
}