DINIC-HDU3599

HDU3599 DINIC+SPFA

这个程序过不了,超时,改成链式前向星应该可以过,这里只说明原理。

2018年6月9日更新:其实只是一个地方没特判,否则就过了,就是特判N=1的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
int n,m;
#define inf 100000000
#define maxn 1505
int a[maxn][maxn],b[maxn][maxn];
int vis[maxn];
int cur[maxn];
int ds[maxn],dt[maxn];
queue<int>q;
int spfa1(){
memset(vis,-1,sizeof(vis));
for(int i=1;i<=n;i++)ds[i]=inf;
while (!q.empty())q.pop();
vis[1]=0;ds[1]=0;
q.push(1);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=-1;
for(int i=1;i<=n;i++){
if(a[u][i]){
if(ds[i]>ds[u]+a[u][i]){
ds[i]=ds[u]+a[u][i];
if(vis[i]<0){q.push(i);vis[i]=0;}
}
}
}
}
}
int spfa2(){
memset(vis,-1,sizeof(vis));
for(int i=1;i<=n;i++)dt[i]=inf;
while (!q.empty())q.pop();
vis[n]=0;dt[n]=0;
q.push(n);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=-1;
for(int i=1;i<=n;i++){
if(a[u][i]){
if(dt[i]>dt[u]+a[u][i]){
dt[i]=dt[u]+a[u][i];
if(vis[i]<0){q.push(i);vis[i]=0;}
}
}
}
}
}
int bfs(){
memset(vis,-1,sizeof(vis));
while (!q.empty()) q.pop();
vis[1]=0;
q.push(1);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=1;i<=n;i++){
if(vis[i]<0 && b[now][i]){
vis[i]=vis[now]+1;
q.push(i);
}
}
}
if(vis[n]<0)
return 0;
return 1;
}
int dfs(int u,int w){
if(u==n)
return w;
int ans=0;
for(int& i=cur[u];i<=n;i++){
if(vis[i]==vis[u]+1&&b[u][i]){
int bs=dfs(i,min(w-ans,b[u][i]));
b[u][i]-=bs;
b[i][u]+=bs;
ans+=bs;
}
}
return ans;
}
int main(){
int t,ca;
cin>>ca;
while(ca--){
cin>>n;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
while(1){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(u+v+w==0)break;
a[u][v]=a[v][u]=w;
}
if(n==1){cout<<0<<endl;continue;}
spfa1();spfa2();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]){
if(ds[i]+dt[j]==ds[n]-a[i][j])
b[i][j]=1;
else if(ds[j]+dt[i]==ds[n]-a[j][i])
b[j][i]=1;
}
int ans=0;
while(bfs()){
for (int i=1;i<=n;i++)
cur[i]=1;
ans+=dfs(1,inf);
}
cout<<ans<<endl;
}
return 0;
}
文章目录
  1. 1. HDU3599 DINIC+SPFA