增广路算法(最大流问题)

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <string>
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include <set>
13 
14 #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
15 #define INF 0x3f3f3f3f
16 #define INFL 0x3f3f3f3f3f3f3f3f
17 #define zero_(x,y) memset(x , y , sizeof(x))
18 #define zero(x) memset(x , 0 , sizeof(x))
19 #define MAX(x) memset(x , 0x3f ,sizeof(x))
20 #define swa(x,y) {LL s;s=x;x=y;y=s;}
21 using namespace std ;
22 #define N 505
23 
24 const double PI = acos(-1.0);
25 typedef long long LL ;
26 
27 int n, np, nc, m, ans;
28 int Map[N][N], pre[N], que[N];
29 bool vis[N];
30 
31 bool bfs(){
32     int head, tail;
33     zero(vis);
34     head = tail = 1;
35     que[tail++] = n;
36     vis[n] = true;
37     while(tail > head){
38         int u = que[head ++];
39         for(int i = 0; i <= n+1; i++){
40             if(!vis[i] && Map[u][i]){
41                 pre[i] = u;
42                 if(i == n+1) return true;
43                 que[tail ++] = i;
44                 vis[i] = true;
45             }
46         }
47     }
48     return false;
49 }
50 
51 void End(){
52     int i, sum = INF;
53     for(i = n + 1; i != n; i = pre[i])
54         sum = min(sum, Map[pre[i]][i]);
55     for(i = n + 1; i != n; i = pre[i]){
56         Map[pre[i]][i] -= sum;
57         Map[i][pre[i]] += sum;
58     }
59     ans += sum;
60 }
61 
62 int main(){
63     //freopen("in.txt","r",stdin);
64     //freopen("out.txt","w",stdout);
65     //ios_base::sync_with_stdio(false); cin.tie(0);
66     int u, v, w;
67     while(~scanf("%d%d%d%d", &n, &np, &nc, &m)){
68         zero(Map);
69         while(m--){
70             while(getchar() != '(');
71             scanf("%d,%d)%d", &u, &v, &w);
72             Map[u][v] += w;
73         }
74         while(np--){
75             while(getchar() != '(');
76             scanf("%d)%d", &u, &w);
77             Map[n][u] = w;
78         }
79         while(nc--){
80             while(getchar() != '(');
81             scanf("%d)%d", &u, &w);
82             Map[u][n+1] = w;
83         }
84         ans = 0;
85         while(bfs()) End();
86         printf("%d\n", ans);
87     }
88     return 0;
89 }

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <string>
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include <set>
13 
14 #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
15 #define INF 0x3f3f3f3f
16 #define INFL 0x3f3f3f3f3f3f3f3f
17 #define zero_(x,y) memset(x , y , sizeof(x))
18 #define zero(x) memset(x , 0 , sizeof(x))
19 #define MAX(x) memset(x , 0x3f ,sizeof(x))
20 #define swa(x,y) {LL s;s=x;x=y;y=s;}
21 using namespace std ;
22 #define N 1005
23 
24 const double PI = acos(-1.0);
25 typedef long long LL ;
26 
27 int n, m, ans;
28 int Map[N][N], pre[N], que[N];
29 bool vis[N];
30 
31 bool bfs(){
32     int head, tail;
33     zero(vis);
34     head = tail = 1;
35     que[tail++] = 2*n;
36     vis[2*n] = true;
37     while(tail > head){
38         int u = que[head ++];
39         for(int i = 0; i <= 2*n+1; i++){
40             if(!vis[i] && Map[u][i]){
41                 pre[i] = u;
42                 if(i == 2*n+1) return true;
43                 que[tail ++] = i;
44                 vis[i] = true;
45             }
46         }
47     }
48     return false;
49 }
50 
51 void End(){
52     int i, sum = INF;
53     for(i = 2*n + 1; i != 2*n; i = pre[i])
54         sum = min(sum, Map[pre[i]][i]);
55     for(i = 2*n + 1; i != 2*n; i = pre[i]){
56         Map[pre[i]][i] -= sum;
57         Map[i][pre[i]] += sum;
58     }
59     ans += sum;
60 }
61 
62 int main(){
63     //freopen("in.txt","r",stdin);
64     //freopen("out.txt","w",stdout);
65     //ios_base::sync_with_stdio(false); cin.tie(0);
66     int u, v;
67     while(~scanf("%d%d", &n, &m)){
68         zero(Map);
69         for(int i = 0; i ){
70             scanf("%d%d", &u, &v);
71             Map[u-1][v-1+n] = 1;
72             Map[2*n][u-1]   = 1;
73             Map[n+v-1][(2*n)+1] = 1;
74         }
75         ans = 0;
76         while(bfs()) End();
77         printf("%d\n", ans);
78     }
79     return 0;
80 }