当前位置：网站首页>Dining (web stream)

Dining (web stream)

2022-08-10 12:16:00 【51CTO】
题目大概：
A farmer has food and drink to feedn头牛,每头牛都有自己喜欢的食物和饮料,其他的不要,Ask the maximum number of cows to feed.
思路：
The template comes from the great god poursoul
The question of this network flow requires two items,That is to match two,Food and drink can be placed on either side of the cow,s--食物--牛--饮料--t,This is how to build a map,Because a cow may go both ways,To limit it,把牛拆成两个点.
So the final map is s 连所有食物容量为1,food even cattle 容量为1,The cow even has its own capacity1,Beef Beverage 容量为1 All drinks includedt 容量为1,Finally, run the maximum flow again.
感想：
Think about what to do when two items match one of the other,and the reason for the dismantling.
代码：
       
       #include <iostream>
       
       #include <cstdio>
       
       #include <cstring>
       
       #define REP(I, X) for(int I = 0; I < X; ++I)
       
       #define FF(I, A, B) for(int I = A; I <= B; ++I)
       
       #define clear(A, B) memset(A, B, sizeof A)
       
       #define copy(A, B) memcpy(A, B, sizeof A)
       
       #define min(A, B) ((A) < (B) ? (A) : (B))
       
       #define max(A, B) ((A) > (B) ? (A) : (B))
       
       using 
       
       namespace 
       
       std;
       
       typedef 
       
       long 
       
       long 
       
       ll;
       
       typedef 
       
       long 
       
       long 
       
       LL;
       
       const 
       
       int 
       
       oo 
       
       = 
       
       0x3f3f3f3f;
       
       const 
       
       int 
       
       maxE 
       
       = 
       
       200000;
       
       const 
       
       int 
       
       maxN 
       
       = 
       
       5005;
       
       const 
       
       int 
       
       maxQ 
       
       = 
       
       10000;
       
       struct 
       
       Edge{
       
       int 
       
       v, 
       
       c, 
       
       n;
       
};
       
       Edge 
       
       edge[
       
       maxE];
       
       int 
       
       adj[
       
       maxN], 
       
       cntE;
       
       int 
       
       Q[
       
       maxE], 
       
       head, 
       
       tail, 
       
       inq[
       
       maxN];
       
       int 
       
       d[
       
       maxN], 
       
       num[
       
       maxN], 
       
       cur[
       
       maxN], 
       
       pre[
       
       maxN];
       
       int 
       
       s, 
       
       t, 
       
       nv;
       
       int 
       
       n, 
       
       m, 
       
       nm;
       
       int 
       
       path[
       
       4][
       
       2] 
       
       = {{
       
       1, 
       
       0}, {
       
       -
       
       1, 
       
       0}, {
       
       0, 
       
       1}, {
       
       0, 
       
       -
       
       1}};
       
       void 
       
       addedge(
       
       int 
       
       u, 
       
       int 
       
       v, 
       
       int 
       
       c){
       
       edge[
       
       cntE].
       
       v 
       
       = 
       
       v; 
       
       edge[
       
       cntE].
       
       c 
       
       = 
       
       c; 
       
       edge[
       
       cntE].
       
       n 
       
       = 
       
       adj[
       
       u]; 
       
       adj[
       
       u] 
       
       = 
       
       cntE
       
       ++;
       
       edge[
       
       cntE].
       
       v 
       
       = 
       
       u; 
       
       edge[
       
       cntE].
       
       c 
       
       = 
       
       0; 
       
       edge[
       
       cntE].
       
       n 
       
       = 
       
       adj[
       
       v]; 
       
       adj[
       
       v] 
       
       = 
       
       cntE
       
       ++;
       
}
       
       void 
       
       REV_BFS(){
       
       clear(
       
       d, 
       
       -
       
       1);
       
       clear(
       
       num, 
       
       0);
       
       head 
       
       = 
       
       tail 
       
       = 
       
       0;
       
       d[
       
       t] 
       
       = 
       
       0;
       
       num[
       
       0] 
       
       = 
       
       1;
       
       Q[
       
       tail
       
       ++] 
       
       = 
       
       t;
       
       while(
       
       head 
       
       != 
       
       tail){
       
       int 
       
       u 
       
       = 
       
       Q[
       
       head
       
       ++];
       
       for(
       
       int 
       
       i 
       
       = 
       
       adj[
       
       u]; 
       
       ~i; 
       
       i 
       
       = 
       
       edge[
       
       i].
       
       n){
       
       int 
       
       v 
       
       = 
       
       edge[
       
       i].
       
       v;
       
       if(
       
       ~d[
       
       v]) 
       
       continue;
       
       d[
       
       v] 
       
       = 
       
       d[
       
       u] 
       
       + 
       
       1;
       
       num[
       
       d[
       
       v]]
       
       ++;
       
       Q[
       
       tail
       
       ++] 
       
       = 
       
       v;
       
        }
       
    }
       
}
       
       int 
       
       ISAP(){
       
       copy(
       
       cur, 
       
       adj);
       
       REV_BFS();
       
       int 
       
       flow 
       
       = 
       
       0, 
       
       u 
       
       = 
       
       pre[
       
       s] 
       
       = 
       
       s, 
       
       i;
       
       while(
       
       d[
       
       s] 
       
       < 
       
       nv){
       
       if(
       
       u 
       
       == 
       
       t){
       
       int 
       
       f 
       
       = 
       
       oo, 
       
       neck;
       
       for(
       
       i 
       
       = 
       
       s; 
       
       i 
       
       != 
       
       t; 
       
       i 
       
       = 
       
       edge[
       
       cur[
       
       i]].
       
       v){
       
       if(
       
       f 
       
       > 
       
       edge[
       
       cur[
       
       i]].
       
       c){
       
       f 
       
       = 
       
       edge[
       
       cur[
       
       i]].
       
       c;
       
       neck 
       
       = 
       
       i;
       
                }
       
            }
       
       for(
       
       i 
       
       = 
       
       s; 
       
       i 
       
       != 
       
       t; 
       
       i 
       
       = 
       
       edge[
       
       cur[
       
       i]].
       
       v){
       
       edge[
       
       cur[
       
       i]].
       
       c 
       
       -= 
       
       f;
       
       edge[
       
       cur[
       
       i] 
       
       ^ 
       
       1].
       
       c 
       
       += 
       
       f;
       
            }
       
       flow 
       
       += 
       
       f;
       
       u 
       
       = 
       
       neck;
       
        }
       
       for(
       
       i 
       
       = 
       
       cur[
       
       u]; 
       
       ~i; 
       
       i 
       
       = 
       
       edge[
       
       i].
       
       n) 
       
       if(
       
       edge[
       
       i].
       
       c 
       
       && 
       
       d[
       
       u] 
       
       == 
       
       d[
       
       edge[
       
       i].
       
       v] 
       
       + 
       
       1) 
       
       break;
       
       if(
       
       ~i){
       
       cur[
       
       u] 
       
       = 
       
       i;
       
       pre[
       
       edge[
       
       i].
       
       v] 
       
       = 
       
       u;
       
       u 
       
       = 
       
       edge[
       
       i].
       
       v;
       
        }
       
       else{
       
       if(
       
       0 
       
       == (
       
       --
       
       num[
       
       d[
       
       u]])) 
       
       break;
       
       int 
       
       mind 
       
       = 
       
       nv;
       
       for(
       
       i 
       
       = 
       
       adj[
       
       u]; 
       
       ~i; 
       
       i 
       
       = 
       
       edge[
       
       i].
       
       n){
       
       if(
       
       edge[
       
       i].
       
       c 
       
       && 
       
       mind 
       
       > 
       
       d[
       
       edge[
       
       i].
       
       v]){
       
       mind 
       
       = 
       
       d[
       
       edge[
       
       i].
       
       v];
       
       cur[
       
       u] 
       
       = 
       
       i;
       
                }
       
            }
       
       d[
       
       u] 
       
       = 
       
       mind 
       
       + 
       
       1;
       
       num[
       
       d[
       
       u]]
       
       ++;
       
       u 
       
       = 
       
       pre[
       
       u];
       
        }
       
    }
       
       return 
       
       flow;
       
}
       
       void 
       
       work()
       
{
       
       int 
       
       f,
       
       d,
       
       nf,
       
       nd;
       
       scanf(
       
       "%d%d%d",
       
       &
       
       n,
       
       &
       
       f,
       
       &
       
       d);
       
       s
       
       =
       
       n
       
       *
       
       2
       
       +
       
       f
       
       +
       
       d,
       
       t
       
       =
       
       s
       
       +
       
       1;
       
       nv
       
       =
       
       t
       
       +
       
       1;
       
       //提前设置好s,t等变量
       
       nf
       
       =
       
       2
       
       *
       
       n;
       
       nd
       
       =
       
       2
       
       *
       
       n
       
       +
       
       f;
       
       clear(
       
       adj, 
       
       -
       
       1);
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       ++
       
       i)
       
    {
       
       int 
       
       f1,
       
       d1,
       
       lf,
       
       ld;
       
       scanf(
       
       "%d%d",
       
       &
       
       f1,
       
       &
       
       d1);
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       f1;
       
       ++
       
       j)
       
        {
       
       scanf(
       
       "%d",
       
       &
       
       lf);
       
       addedge(
       
       nf
       
       +
       
       lf
       
       -
       
       1,
       
       i,
       
       1);
       
        }
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       d1;
       
       ++
       
       j)
       
        {
       
       scanf(
       
       "%d",
       
       &
       
       ld);
       
       addedge(
       
       n
       
       +
       
       i,
       
       nd
       
       +
       
       ld
       
       -
       
       1,
       
       1);
       
        }
       
    }
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       f;
       
       ++
       
       i)
       
    {
       
       addedge(
       
       s,
       
       nf
       
       +
       
       i,
       
       1);
       
    }
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       d;
       
       ++
       
       i)
       
    {
       
       addedge(
       
       nd
       
       +
       
       i,
       
       t,
       
       1);
       
    }
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       ++
       
       i)
       
    {
       
       addedge(
       
       i,
       
       i
       
       +
       
       n,
       
       1);
       
    }
       
       printf(
       
       "%d\n",
       
       ISAP());
       
}
       
       int 
       
       main()
       
{
       
       work();
       
       return 
       
       0;
       
}
      
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.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
原网站
版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/222/202208101129429936.html
当前位置：网站首页>Dining (web stream)

Dining (web stream)

边栏推荐

猜你喜欢

随机推荐
