最短路+最大流
刚开始没有理解题意,总感觉求一个最大流不就行了吗?
原来真正的题意是,最短路始终不变的。我们每一次必须从最短路走。
正确的做法是,我们正反方向求一次最短路。
然后,枚举边。如果边<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; } }