题目链接
HDU-3416
题意
给定n节点，m单向带权边，从s到t，只能走最短路，每条路只能走一次，请问最多能到达t几次（不用从t返回s）
思路
开始以为是最小费用流，其实是最短路加最大流。抛开走最短的限制，那么就是裸的最大流，边权设为1，跑dinic就可以了。
关键在于如何确定哪些边是最短的。对于u->v的权为w的边，当且仅当dis1[u]+dis2[v]+w==dis1[t]时，这条边是最短路的边。用语言描述就是：从起点到u的最小距离+边权+v到终点的最小距离=起点到终点的最小距离。其中dis2[v]是通过反向建图跑反向最短路跑出来的，关于反向建图可以参考我之前的题解 POJ-3268。
那么现在思路就很清晰了，正向反向两次建图两次最短路处理出dis1和dis2两个数组，之后枚举每一条边，判断他是否是最短路内的边，如果是就加入到网络流图内。最后跑一遍dinic求出最大流就可以了。
PS：HDU交代码带中文注释容易CE，报错还是特别莫名其妙的报错。。坑死我了。还有DEVcpp这个编译器是真不行，一步步调试的答案和直接编译运行的答案完全不一样，真是离谱儿。
代码
#include<iostream>
#include<queue>
#include<cstring>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;typedef pair <int,int> P;const int maxn=1050;const int maxe=105005;const int inf=0x3f3f3f3f;int head1[maxn],head2[maxn],head3[maxn];//正向图，反向图，网络流图 struct Edge{int to;int next;int w;} edge1[maxe],edge2[maxe],edge3[maxe];//正向图，反向图，网络流图 int cnt,cnt2;int maxflow,s,t,n,m;int dis1[maxn],dis2[maxn];//正向图反向图 int deep[maxn];//层级数int now[maxe];//当前弧优化void init(){cnt=cnt2=0;memset(head1,-1,sizeof(head1));memset(head2,-1,sizeof(head2));memset(head3,-1,sizeof(head3));maxflow=0;return ;}inline void add(int u,int v,int w){//正向建图edge1[cnt].next=head1[u];edge1[cnt].to=v;edge1[cnt].w=w;head1[u]=cnt;//反向建图edge2[cnt].next=head2[v];edge2[cnt].to=u;edge2[cnt].w=w;head2[v]=cnt;cnt++;}inline void add2(int u,int v,int w){//网络流建图edge3[cnt2].next=head3[u];edge3[cnt2].to=v;edge3[cnt2].w=w;head3[u]=cnt2;cnt2++;} void dij1(int start){//正向dijmemset(dis1,0x3f,sizeof(dis1));priority_queue<P,vector<P>,greater<P> > q;dis1[start]=0;q.push(P(0,start));while(!q.empty()){P p=q.top(); q.pop();int v=p.second;if(dis1[v]<p.first) continue;for(int i=head1[v];i!=-1;i=edge1[i].next){int tmp=edge1[i].to;if(dis1[tmp]>dis1[v]+edge1[i].w){dis1[tmp]=dis1[v]+edge1[i].w;q.push(P(dis1[tmp],tmp));}}}return ;}void dij2(int start){//反向dijmemset(dis2,0x3f,sizeof(dis2));priority_queue<P,vector<P>,greater<P> > q;dis2[start]=0;q.push(P(0,start));while(!q.empty()){P p=q.top(); q.pop();int v=p.second;if(dis2[v]<p.first) continue;for(int i=head2[v];i!=-1;i=edge2[i].next){int tmp=edge2[i].to;if(dis2[tmp]>dis2[v]+edge2[i].w){dis2[tmp]=dis2[v]+edge2[i].w;q.push(P(dis2[tmp],tmp));}}}return ;}//网络流部分inline bool bfs(){memset(deep,0x3f,sizeof(deep));queue<int>q;q.push(s);deep[s] = 0;now[s] = head3[s];while(q.size()){int x = q.front();q.pop();for(int i=head3[x];i!=-1;i=edge3[i].next){int y=edge3[i].to;if(edge3[i].w>0&&deep[y]==inf){q.push(y);now[y]=head3[y];deep[y]=deep[x]+1;if(y==t) return 1;}}}return 0;}ll dfs(int x,int flow){if(x==t) return flow;ll ans = 0,k,i;for(i=now[x];i!=-1&&flow;i=edge3[i].next){now[x]=i;int y=edge3[i].to;if(edge3[i].w>0&&(deep[y]==deep[x]+1)){k=dfs(y,min(flow,edge3[i].w));if(!k) deep[y]=inf;edge3[i].w-=k;edge3[i^1].w+=k;ans+=k;flow-=k;}}return ans;} void dinic(){while(bfs())maxflow+=dfs(s,inf);}int main(){IOSint tn;cin>>tn;while(tn--){init();cin>>n>>m;while(m--){int u,v,w;cin>>u>>v>>w;add(u,v,w);}cin>>s>>t;dij1(s),dij2(t);for(int i=1;i<=n;i++)for(int j=head1[i];~j;j=edge1[j].next){//前向星遍历int w=edge1[j].w,to=edge1[j].to;if(dis1[i]+dis2[to]+w==dis1[t]){add2(i,to,1);add2(to,i,0);}}dinic();cout<<maxflow<<endl;}return 0;}