关于费用流的修正

以：BZOJ 1927: [Sdoi2010]星际竞速为例

以前我写的：

注意updata()函数

View Code

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 
 7 #define N 10000
 8 #define M 1000000
 9 
10 using namespace std;
11 
12 int head[N],next[M],to[M],pr[M],len[M];
13 int q[M*5],dis[N],pre[N];
14 bool vis[N];
15 int n,m,cnt,S,T;
16 
17 inline void add(int u,int v,int r,int w)
18 {
19     to[cnt]=v; len[cnt]=r; pr[cnt]=w; next[cnt]=head[u]; head[u]=cnt++;
20     to[cnt]=u; len[cnt]=0; pr[cnt]=-w; next[cnt]=head[v]; head[v]=cnt++;
21 }
22 
23 inline void read()
24 {
25     memset(head,-1,sizeof head); cnt=0;
26     scanf("%d%d",&n,&m);
27     S=0; T=2*n+1;
28     for(int i=1,a;i<=n;i++)
29     {
30         scanf("%d",&a);
31         add(S,i+n,1,a);
32     }
33     for(int i=1,a,b,c;i<=m;i++)
34     {
35         scanf("%d%d%d",&a,&b,&c);
36         if(a>b) swap(a,b);
37         add(a,b+n,1,c);
38     }
39     for(int i=1;i<=n;i++) add(S,i,1,0),add(i+n,T,1,0);
40 }
41 
42 inline bool spfa()
43 {
44     memset(dis,0x3f,sizeof dis);
45     memset(pre,-1,sizeof pre);
46     int h=1,t=2,sta;
47     q[1]=S; vis[S]=true; dis[S]=0;
48     while(h<t)
49     {
50         sta=q[h++]; vis[sta]=false;
51         for(int i=head[sta];~i;i=next[i])
52             if(len[i]&&dis[to[i]]>dis[sta]+pr[i])
53             {
54                 dis[to[i]]=dis[sta]+pr[i];
55                 pre[to[i]]=i;
56                 if(!vis[to[i]]) vis[to[i]]=true,q[t++]=to[i];
57             }
58     }
59     return pre[T]!=-1;
60 }
61 
62 inline void updata()
63 {
64     for(int i=pre[T];~i;i=pre[to[i^1]])
65     {
66         len[i]-=1; len[i^1]+=1;
67     }
68 }
69 
70 inline void go()
71 {
72     int ans=0;
73     while(spfa()) ans+=dis[T],updata();
74     printf("%d\n",ans);
75 }
76 
77 int main()
78 {
79     read();
80     go();
81     return 0;
82 }

同学提醒我后，我改良的：

同样注意updata()与之前的不同

View Code

 1 #include <iostream> 
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <algorithm>
 6 
 7 #define N 2000
 8 #define M 200000
 9 #define INF 1e9
10 
11 using namespace std;
12 
13 int head[N],next[M],to[M],len[M],pr[M];
14 int dis[N],pre[N],q[M],mlen;
15 bool vis[N];
16 int n,m,T,S,cnt;
17 
18 inline void add(int u,int v,int r,int w)
19 {
20     to[cnt]=v; len[cnt]=r; pr[cnt]=w; next[cnt]=head[u]; head[u]=cnt++;
21     to[cnt]=u; len[cnt]=0; pr[cnt]=-w; next[cnt]=head[v]; head[v]=cnt++;
22 }
23 
24 inline void read()
25 {
26     memset(head,-1,sizeof head); cnt=0;
27     S=0; T=n+n+1;
28     for(int i=1,val;i<=n;i++)
29     {
30         scanf("%d",&val);
31         add(S,i,1,0);
32         add(S,i+n,1,val);
33         add(i+n,T,1,0);
34     }
35     for(int i=1,a,b,c;i<=m;i++)
36     {
37         scanf("%d%d%d",&a,&b,&c);
38         if(a>b) swap(a,b);
39         add(a,b+n,1,c);
40     }
41 }
42 
43 inline bool spfa()
44 {
45     memset(pre,-1,sizeof pre);
46     memset(dis,0x3f,sizeof dis);
47     q[1]=S; vis[S]=true; dis[S]=0;
48     int h=1,t=2,sta;
49     while(h<t)
50     {
51         sta=q[h++]; vis[sta]=false;
52         for(int i=head[sta];~i;i=next[i])
53             if(len[i]&&dis[to[i]]>dis[sta]+pr[i])
54             {
55                 dis[to[i]]=dis[sta]+pr[i];
56                 pre[to[i]]=i;
57                 if(!vis[to[i]]) vis[to[i]]=true,q[t++]=to[i];
58             }
59     }
60     return pre[T]!=-1;
61 }
62 
63 inline void updata()
64 {
65     mlen=INF;
66     for(int i=pre[T];~i;i=pre[to[i^1]])
67         mlen=min(mlen,len[i]);
68     for(int i=pre[T];~i;i=pre[to[i^1]])
69         len[i]-=mlen,len[i^1]+=mlen;
70 }
71 
72 inline void go()
73 {
74     int ans=0;
75     while(spfa()) updata(),ans+=mlen*dis[T];
76     printf("%d\n",ans);
77 }
78 
79 int main()
80 {
81     while(scanf("%d%d",&n,&m)!=EOF) read(),go();
82     return 0;
83 }

但是最可恨的是上面那个代码竟然在所有我做的费用流中都跑的非常快。。。抑郁。。。

关于 费用流 的修正

关于费用流的修正