P2207 上学路线route
正反两遍spfa，判断某条边是否是在最短路上，如果是的话就建边，跑最大流
1 #include<cstdio>View Code
2 #include<queue>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 #define maxn 250000
7 #define inf 0x3f3f3f3f
8 int n,m,src,dec,ans,cur[maxn],d[maxn],ansx,y,z,num,front2[maxn*2];
9 int lev[maxn],front[maxn*2],head,tail,que[maxn*2],tot=1,dis[maxn],dis1[maxn];
10 bool vis[maxn];
11 struct node{
12 int to,next,cap;
13 }e[maxn*2];
14
15 struct Edge{
16 int u,v,next,w,d;
17 }edge[maxn*2],edge2[maxn*2];
18
19 inline void add(int u,int v,int w)
20 {
21 e[++tot].to=v; e[tot].next=front[u]; e[tot].cap=w; front[u]=tot;
22 e[++tot].to=u; e[tot].next=front[v]; e[tot].cap=0; front[v]=tot;
23 }
24
25 void ins(int u,int v,int w,int d)
26 {
27 edge[++num].v=v;
28 edge[num].w=w;
29 edge[num].u=u;
30 edge[num].next=front2[u];
31 edge[num].d=d;
32 front2[u]=num;
33 }
34
35 char ch;
36 inline void read(int &now)
37 {
38 ch=getchar(); now=0;
39 while(ch>'9'||ch<'0') ch=getchar();
40 while(ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar();
41 }
42
43 bool bfs()
44 {
45 for(int i=src;i<=dec;i++) lev[i]=-1,cur[i]=front[i];
46 head=tail=0;
47 que[tail++]=src; lev[src]=0;
48 while(head<tail)
49 {
50 for(int i=front[que[head]];i;i=e[i].next)
51 if(e[i].cap>0&&lev[e[i].to]==-1)
52 {
53 lev[e[i].to]=lev[que[head]]+1;
54 que[tail++]=e[i].to;
55 if(e[i].to==dec) return true;
56 }
57 head++;
58 }
59 return false;
60 }
61
62 void spfa(int s)
63 {
64 queue<int>q;
65 for(int i=1;i<=n;i++) dis[i]=inf;
66 memset(vis,false,sizeof(false));
67 vis[s]=1; dis[s]=0;
68 q.push(s);
69 while(!q.empty())
70 {
71 int cur=q.front(); q.pop();
72 for(int i=front2[cur];i;i=edge[i].next)
73 {
74 if(dis[edge[i].v]>dis[cur]+edge[i].w)
75 {
76 dis[edge[i].v]=dis[cur]+edge[i].w;
77 if(!vis[edge[i].v])
78 {
79 vis[edge[i].v]=1;
80 q.push(edge[i].v);
81 }
82 }
83 }
84 vis[cur]=false;
85 }
86 }
87
88 int dinic(int u,int flow)
89 {
90 if(u==dec) return flow;
91 int res=0,delta;
92 for(int i=cur[u];i;i=e[i].next)
93 {
94 if(e[i].cap>0&&lev[e[i].to]>lev[u])
95 {
96 delta=dinic(e[i].to,min(e[i].cap,flow-res));
97 if(delta)
98 {
99 e[i].cap-=delta; e[i^1].cap+=delta;
100 res+=delta; if(res==flow) break;
101 }
102 }
103 }
104 if(res!=flow) lev[u]=-1;
105 return res;
106 }
107
108 int main()
109 {
110 read(n); read(m);
111 for(int i=1;i<=m;i++)
112 {
113 int u,v,w,d;
114 read(u); read(v); read(w); read(d);
115 edge2[i].u=u; edge2[i].v=v; edge2[i].w=w; edge2[i].d=d;
116 ins(u,v,w,d);
117 ins(v,u,w,d);
118 }
119 src=1; dec=n;
120 spfa(src);
121 printf("%d\n",dis[n]);
122 for(int i=1;i<=n;i++) dis1[i]=dis[i];
123 spfa(dec);
124 for(int i=1;i<=m;i++)
125 {
126 if(dis1[edge2[i].u]<dis1[edge2[i].v])
127 {
128 if(edge2[i].w+dis1[edge2[i].u]+dis[edge2[i].v]==dis1[n])
129 add(edge2[i].u,edge2[i].v,edge2[i].d);
130 }
131 else{
132 if(edge2[i].w+dis1[edge2[i].v]+dis[edge2[i].u]==dis1[n])
133 add(edge2[i].v,edge2[i].u,edge2[i].d);
134 }
135 }
136 while(bfs())
137 ans+=dinic(src,inf);
138 printf("%d\n",ans);
139 return 0;
140 }