POJ 1459 ZOJ 1734 Power Network dinic 算法网络流

裸的网络流，就是在读数据的时候，注意用while(getchar()!='(');scanf("%d,%d),%d");

然后增加超源点与超收点。我是用dinic算法，速度慢，跑了549貌似ms，貌似，希望能优化，用个什么预流推进算法试试啊。

在纠结了很久后，终于在书上把预流推进算法抄下来了，哈哈，调试了很久，一直陷入死循环，后来一看输入文件不是这个题的输入，想shi啊，有木有

贴代码 dinic 算法：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAXN 108
 4 #define INF 300000000
 5 int n,np,nc,m;
 6 int s ;//源点
 7 int t; //汇点
 8 int map[MAXN][MAXN];//容量网络
 9 bool sign[MAXN][MAXN];//层次网络
10 void init()
11 {
12     int i;
13     int u,v,z;
14     s = n;
15     t = n+1;
16     memset(map,0,sizeof(map));
17     for(i=0; i<m; ++i)
18     {
19         while(getchar() != '(');
20         scanf("%d,%d)%d",&u,&v,&z);
21         map[u][v] = z;
22     }
23     for(i=0; i<np; ++i)
24     {
25         while(getchar() != '(');
26         scanf("%d)%d",&u,&z);
27         map[s][u] = z;
28     }
29     for(i =0; i<nc; ++i)
30     {
31         while(getchar() != '(');
32         scanf("%d)%d",&u,&z);
33         map[u][t] = z;
34     }
35 }
36 int min(int x,int y)
37 {
38     return x<y ? x : y;
39 }
40 bool BFS()
41 {
42     bool used[MAXN];
43     int queue[MAXN];
44     int fr=0,ta=0;
45     int i;
46     memset(used,0,sizeof(used));
47     memset(sign,0,sizeof(sign));
48     queue[ta++] = s;
49     used[s] = 1;
50     while(fr != ta)
51     {
52         int v = queue[fr++];
53         for(i=0; i<=n+1; ++i)
54         {
55             if(!used[i] && map[v][i])
56             {
57                 queue[ta++] = i;
58                 sign[v][i] = 1;
59                 used[i] = 1;
60             }
61         }
62     }
63     return used[t];
64 }
65 int  DFS(int v,int sum)
66 {
67     int i,r,f;
68     if(v == t) return sum;
69     r = sum;
70     for(i=0; i<=n+1; ++i)
71     {
72         if(sign[v][i])
73         {
74             f=DFS(i,min(map[v][i],sum));
75             map[v][i] -=f;
76             map[i][v] += f;
77             sum -= f;
78         }
79     }
80     return r-sum;
81 }
82 int main()
83 {
84 //    freopen("in.cpp","r",stdin);
85     while(~scanf("%d%d%d%d",&n,&np,&nc,&m))
86     {
87         init();
88         int ans = 0;
89         while(BFS()) ans += DFS(s,INF);
90         printf("%d\n",ans);
91     }
92     return 0;
93 }

预流推进算法，只跑了150ms,貌似：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #define MAXN 110
 5 #define INF 0x7fffffff  //相当于21，4748，3647
 6 using namespace std;
 7 int s,t; //源点和汇点
 8 queue<int> act;
 9 int h[MAXN];  //高度
10 int ef[MAXN]; //余流，能流出去多少
11 int n,np,nc,m;
12 int resi[MAXN][MAXN];//残留网络，每条边的权值表示容量
13 int min(int x,int y)
14 {
15     if(x <y)return x;
16     else return y;
17 }
18 void pushRelabel()
19 {
20     int i;
21     int sum=0;
22     int u,p;
23     memset(ef,0,sizeof(ef));
24     memset(h,0,sizeof(h));
25     h[s] = n+2;
26     ef[s] = INF;//源点能往外流正无穷
27     ef[t] = -INF;//汇点不能往外流，所以汇点能往外流负无穷
28     act.push(s);
29     while(!act.empty())
30     {
31         u = act.front();
32         act.pop();
33         for(i=0; i<=n+1; ++i)
34         {
35             p = min(resi[u][i],ef[u]);
36             if(p > 0 && (u==s || h[u] == h[i]+1))
37             {
38                 resi[u][i] -= p;
39                 resi[i][u] += p;
40                 ef[u] -= p;
41                 ef[i] += p;
42                 if(i == t) sum += p;
43                 if(i != s && i!=t)
44                     act.push(i);
45             }
46         }
47         if(u != s && u != t && ef[u] > 0)
48         {
49             h[u]++;
50             act.push(u);
51         }
52     }
53     printf("%d\n",sum);
54 }
55 int main()
56 {
57 //    freopen("in.cpp","r",stdin);
58     int i;
59     int u,v,val;
60     while(~scanf("%d%d%d%d",&n,&np,&nc,&m))
61     {
62         s = n;
63         t = n+1;
64         memset(resi,0,sizeof(resi));
65         for(i=0; i<m; ++i)
66         {
67             while(getchar()!='(');
68             scanf("%d,%d)%d",&u,&v,&val);
69             resi[u][v] = val;
70         }
71         for(i=0; i<np; ++i)
72         {
73             while(getchar()!='(');
74             scanf("%d)%d",&u,&val);
75             resi[s][u] = val;
76         }
77         for(i=0; i<nc; ++i)
78         {
79             while(getchar()!='(');
80             scanf("%d)%d",&u,&val);
81             resi[u][t] = val;
82         }
83         pushRelabel();
84     }
85     return 0;
86 }

POJ 1459 ZOJ 1734 Power Network dinic 算法 网络流

POJ 1459 ZOJ 1734 Power Network dinic 算法网络流