过得好辛苦，T了一版QAQ
思路不难想，先spfa然后把最短路挑出来再来个最大流。。
然而我却把最短路和最大流混在一起做，怪不得那么慢。。花了好多时间啊QAQ
叫我偷懒 叫我偷懒 叫我偷懒
1 #include<bits/stdc++.h> 2 #define inc(i,l,r) for(int i=l;i<=r;i++) 3 #define dec(i,l,r) for(int i=l;i>=r;i--) 4 #define link(x) for(edge *j=h[x];j;j=j->next) 5 #define _link(x) for(edge *j=_h[x];j;j=j->next) 6 #define mem(a) memset(a,0,sizeof(a)) 7 #define inf 0x7ffffff 8 #define ll long long 9 #define succ(x) (1<<x) 10 #define NM 1000+5 11 #define nm 500000 12 using namespace std; 13 int read(){ 14 int x=0,f=1;char ch=getchar(); 15 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} 16 while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); 17 return x*f; 18 } 19 struct edge{ 20 int t,v,d; 21 edge *next,*rev; 22 }e[nm],*h[NM],_e[nm],*_h[NM],*p=_e; 23 void _add(int x,int y,int d,int v){ 24 p->t=y;p->v=v;p->d=d;p->next=_h[x];_h[x]=p;p++; 25 } 26 void __add(int x,int y,int v){ 27 p->t=y;p->v=v;p->next=h[x];h[x]=p;p++; 28 } 29 void add(int x,int y,int v){ 30 __add(x,y,v);__add(y,x,0); 31 h[x]->rev=h[y];h[y]->rev=h[x]; 32 } 33 int n,m,s,ans,_x,_y,_t,_v,v[NM],d[NM]; 34 queue<int >q; 35 int spfa(){ 36 mem(d);mem(v); 37 inc(i,1,n)d[i]=inf; 38 d[1]=0;v[1]++;q.push(1); 39 while(!q.empty()){ 40 int t=q.front();q.pop();v[t]=false; 41 _link(t) 42 if(d[j->t]>d[t]+j->d){ 43 d[j->t]=d[t]+j->d; 44 if(!v[j->t])v[j->t]++,q.push(j->t); 45 } 46 } 47 return d[n]; 48 } 49 int bfs(){ 50 mem(v);mem(d); 51 v[1]++;q.push(1);d[1]++; 52 while(!q.empty()){ 53 int t=q.front();q.pop(); 54 link(t) 55 if(j->v&&(!d[j->t]||d[j->t]>d[t]+1)){ 56 d[j->t]=d[t]+1; 57 if(!v[j->t])q.push(j->t),v[j->t]++; 58 } 59 } 60 return d[n]; 61 } 62 int dfs(int x,int k){ 63 int _a; 64 if(x==n)return k; 65 link(x) 66 if(j->v&&d[j->t]==d[x]+1&&(_a=dfs(j->t,min(j->v,k)))){ 67 j->v-=_a;j->rev->v+=_a;return _a; 68 } 69 return 0; 70 } 71 int main(){ 72 n=read();m=read(); 73 inc(i,1,m){ 74 _x=read();_y=read();_t=read();_v=read(); 75 _add(_x,_y,_t,_v);_add(_y,_x,_t,_v); 76 } 77 printf("%d ",s=spfa());p=e; 78 inc(i,1,n) 79 _link(i) 80 if(d[j->t]==d[i]+j->d) 81 add(i,j->t,j->v); 82 while(bfs()) 83 if(_t=dfs(1,inf))ans+=_t; 84 printf("%d ",ans); 85 return 0; 86 }