\u5f88\u663e\u7136\u9996\u5148spfa\u51fa\u6700\u77ed\u8def\uff0c\u7136\u540e\u5c31\u6309\u6700\u77ed\u8def\u5efa\u56fe\uff0c\u7136\u540e\u5f88\u663e\u7136\u5c31\u6362\u6210\u4e86\u6700\u5c0f\u5272\u7684\u95ee\u9898\u4e86\u56e7\u3002\u3002\u4e0d\u8fc7\u8fd9\u91cc\u7684\u5272\u662f\u6709\u5411\u7684\uff0c\u6ce8\u610f\u4e00\u4e0b\u54e6(*^__^*) \u563b\u563b
Code:<\/p>\n
#include<cstdio>#include<queue>#include<algorithm>#include<iostream>using namespace std;const int maxn=500;struct Edge{ int t,c,Len; bool e; Edge(int _t,int _Len,int _c,Edge* _next): t(_t),Len(_Len),next(_next),c(_c),e(false){} Edge*next,*op; \/*void addFlow(int _c) { c-=_c; op->c+=_c; }*\/}*E[maxn];int n,m,vs,vt;void InsEdge(int s,int t,int c,int Len){ E[s]=new Edge(t,Len,c,E[s]); E[t]=new Edge(s,Len,c,E[t]); E[s]->op=E[t];E[t]->op=E[s];}void Init(){ scanf("%d %d",&n,&m);int s,t,Len,c; vs=0,vt=n-1; while(m–) { scanf("%d %d %d %d",&s,&t,&Len,&c); InsEdge(s-1,t-1,c,Len); }}const int inf=~0U>>2;int DistToStart[maxn],DistToEnd[maxn];void Spfa(int Dist[maxn],int vs){ queue<int> Q; bool inQ[maxn]={0}; for(int i=0;i<n;i++) Dist[i]=inf; Dist[vs]=0;inQ[vs]=true;Q.push(vs); while(Q.size()) { int t=Q.front();Q.pop();inQ[t]=false;int cost=Dist[t]; for(Edge*i=E[t];i;i=i->next) { int ncost=cost+i->Len; if(ncost<Dist[i->t]) { Dist[i->t]=ncost; if(!inQ[i->t]) inQ[i->t]=true,Q.push(i->t); } } }}void BuildGraph(){ Spfa(DistToStart,vs); Spfa(DistToEnd,vt); int cost=DistToStart[vt]; for(int i=0;i<n;i++) for(Edge*e=E[i];e;e=e->next) if(DistToStart[i]+e->Len+DistToEnd[e->t]==cost) { e->e=true; e->op->e=true; e->op->c=0; } cout<<cost<<endl;}int h[maxn],vh[maxn],v;int aug(int no,int m){ if(no==vt) return m; int l=m; for(Edge*i=E[no];i;i=i->next)if(i->e&&i->c&&h[no]==h[i->t]+1) { int d=aug(i->t,min(l,i->c)); i->c-=d,i->op->c+=d,l-=d; if(!l||h[vs]>=v) return m-l; } int minh=v; for(Edge*i=E[no];i;i=i->next)if(i->e&&i->c) minh=min(minh,h[i->t]+1); if(!–vh[h[no]]) h[vs]=v; vh[h[no]=minh]++; return m-l;}long long CalFlow(){ memset(h,0,sizeof(h)); memset(vh,0,sizeof(vh)); v=n;vh[0]=v;long long flow=0; while(h[vs]<v) flow+=aug(vs,inf); return flow;}int main(){ \/\/freopen("in","r",stdin); Init(); BuildGraph(); cout<<CalFlow()<<endl;} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u5f88\u663e\u7136\u9996\u5148spfa\u51fa\u6700\u77ed\u8def\uff0c\u7136\u540e\u5c31\u6309\u6700\u77ed\u8def\u5efa\u56fe\uff0c\u7136\u540e\u5f88\u663e\u7136\u5c31\u6362\u6210\u4e86\u6700\u5c0f\u5272\u7684\u95ee\u9898\u4e86\u56e7\u3002\u3002\u4e0d\u8fc7\u8fd9\u91cc\u7684\u5272\u662f\u6709\u5411\u7684\uff0c\u6ce8\u610f\u4e00\u4e0b\u54e6(*^__^*) \u563b\u563bCode: #include<cstdio>#include<queue>#include<algorithm>#include<iostream>using namespace std;const int maxn=500;struct Edge{ int t,c,Len; bool e; Edge(int _t,int _Len,int _c,Edge* _next): t(_t),Len(_Len),next(_next),c(_c),e(false){} Edge*next,*op; \/*void addFlow(int _c) { c-=_c; op->c+=_c; }*\/}*E[maxn];int n,m,vs,vt;void InsEdge(int s,int t,int c,int Len){ E[s]=new Edge(t,Len,c,E[s]); E[t]=new Edge(s,Len,c,E[t]); E[s]->op=E[t];E[t]->op=E[s];}void Init(){ scanf("%d %d",&n,&m);int s,t,Len,c; vs=0,vt=n-1; while(m–) { scanf("%d %d %d %d",&s,&t,&Len,&c); InsEdge(s-1,t-1,c,Len); }}const int inf=~0U>>2;int DistToStart[maxn],DistToEnd[maxn];void Spfa(int Dist[maxn],int […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/185"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=185"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/185\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}