当前位置：网站首页>Dining （网络流）

Dining （网络流）

2022-08-10 11:31:00 【51CTO】
题目链接: http://poj.org/problem?id=3281
题目大概：
一个农夫有食物和饮料来喂养n头牛，每头牛都有自己喜欢的食物和饮料，其他的不要，问最多养活几头牛。
思路：
模板来自大神 poursoul
这个网络流的题牛需要两样物品，也就是要匹配两个，可以把食物和饮料放到牛的两边，s--食物--牛--饮料--t，这样来建图，因为一头牛可能会走通两条路，为了限制一下，把牛拆成两个点。
所以最后建图就是 s 连所有食物容量为1，食物连牛容量为1，牛自己连自己容量为1，牛连饮料容量为1 所有饮料连t 容量为1，最后跑一遍最大流即可。
感想：
思考两种物品匹配一种时的做法，和拆点的原因。
代码：
       
       #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://blog.51cto.com/u_15747246/5563000
当前位置：网站首页>Dining （网络流）

Dining （网络流）

边栏推荐

猜你喜欢

随机推荐
