Article From:https://www.cnblogs.com/Blogggggg/p/9061363.html

Title Link:https://cn.vjudge.net/problem/UVA-10779

Preface:

  This topic is about Jiang Zhihao’s notes on some modeling methods of network flow.

Knowledge point: maximum flow

An excerpt from the question:

  \(Bob\) And his friends collect stickers from the candy wrapper. \ (Bob\) and his friend a total of \ (n\) people. There is a total of \ (m\) different stickers.

  Each person has some stickers that may be repeated, and he only exchanges the stickers he does not have with others. The stickers are always on one – to – one exchange.

  \(Bob\) Smarter than these friends, because he realized that it’s not always the best way to exchange only the stickers that he doesn’t have with others. In some cases, it is more cost-effective to get a duplicate sticker.

  Suppose Bob\’s friends exchange only with \ (Bob\), and these friends will only sell repeated stickers in hand to exchange the different stickers they don’t have. Your task is to help Bob\ calculate the maximum number of stickers that he can get in the end.Number。

  \((2 \le n le 10, 5 \le m \le 25)\)

The idea of solving the problem:

  Each sticker and every friend is regarded as a point, plus a source point and a sink point.

  For each type of sticker, the number of sheets from the source point to the sticker is set to Bob\.

  For every friend, if he does not have some kind of sticker, build a line from the sticker to his side, with the capacity of \ (1\); if he has the sticker and the amount of (k\) is greater than / (1\), build a side from him to the sticker, with the capacity of \ (k-1\).

  For each type of sticker, build a side to sink point with capacity of (1\).

ACCode:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int MAXN = 510;//Maximum number of points
  4 const int MAXM = 15000;//Maximum value of the number of edges
  5 const int INF = 0x3f3f3f3f;
  6 
  7 struct Edge{
  8     int to,next,cap,flow;
  9 }edge[MAXM];//Attention is MAXM
 10 int tol;
 11 int head[MAXN];
 12 int gap[MAXN],dep[MAXN],cur[MAXN];
 13 void init(){
 14     tol = 0;
 15     memset(head,-1,sizeof(head));
 16 }
 17 void addedge(int u,int v,int w,int rw = 0){
 18     edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
 19     edge[tol].next = head[u]; head[u] = tol++;
 20     edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
 21     edge[tol].next = head[v]; head[v] = tol++;
 22 }
 23 int Q[MAXN];
 24 void BFS(int start,int end){
 25     memset(dep,-1,sizeof(dep));
 26     memset(gap,0,sizeof(gap));
 27     gap[0] = 1;
 28     int front = 0, rear = 0;
 29     dep[end] = 0;
 30     Q[rear++] = end;
 31     while(front != rear){
 32         int u = Q[front++];
 33         for(int i = head[u]; i != -1; i = edge[i].next){
 34             int v = edge[i].to;
 35             if(dep[v] != -1)
 36                 continue;
 37             Q[rear++] = v;
 38             dep[v] = dep[u] + 1;
 39             gap[dep[v]]++;
 40         }
 41     }
 42 }
 43 int S[MAXN];
 44 int sap(int start,int end,int N){
 45     BFS(start,end);
 46     memcpy(cur,head,sizeof(head));
 47     int top = 0;
 48     int u = start;
 49     int ans = 0;
 50     while(dep[start] < N){
 51         if(u == end){
 52             int Min = INF;
 53             int inser;
 54             for(int i = 0;i < top;i++)
 55                 if(Min > edge[S[i]].cap - edge[S[i]].flow){
 56                     Min = edge[S[i]].cap - edge[S[i]].flow;
 57                     inser = i;
 58                 }
 59             for(int i = 0;i < top;i++){
 60                 edge[S[i]].flow += Min;
 61                 edge[S[i]^1].flow -= Min;
 62             }
 63             ans += Min;
 64             top = inser;
 65             u = edge[S[top]^1].to;
 66             continue;
 67         }
 68         bool flag = false;
 69         int v;
 70         for(int i = cur[u]; i != -1; i = edge[i].next){
 71             v = edge[i].to;
 72             if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
 73                 flag = true;
 74                 cur[u] = i;
 75                 break;
 76             }
 77         }
 78         if(flag){
 79             S[top++] = cur[u];
 80             u = v;
 81             continue;
 82         }
 83         int Min = N;
 84         for(int i = head[u]; i != -1; i = edge[i].next)
 85             if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){
 86                 Min = dep[edge[i].to];
 87                 cur[u] = i;
 88             }
 89         gap[dep[u]]--;
 90         if(!gap[dep[u]])
 91             return ans;
 92         dep[u] = Min + 1;
 93         gap[dep[u]]++;
 94         if(u != start)
 95             u = edge[S[--top]^1].to;
 96     }
 97     return ans;
 98 }
 99 int has[30];
100 int main(){
101     int T;
102     int n,m,k;
103     int num;
104     int kase=1;
105     scanf("%d",&T);
106     while(T--){
107         init();
108         int s=0,t=MAXN-1;
109         memset(has,0,sizeof(has));
110         scanf("%d%d",&n,&m);
111         scanf("%d",&k);
112         while(k--){
113             scanf("%d",&num);
114             has[num]++;
115         }
116         for(int i=1;i<=m;i++){
117             addedge(s,i,has[i]);
118             addedge(i,t,1);
119         }
120         for(int i=1;i<n;i++){
121             memset(has,0,sizeof(has));
122             scanf("%d",&k);
123             while(k--){
124                 scanf("%d",&num);
125                 has[num]++;
126             }
127             for(int j=1;j<=m;j++){
128                 if(!has[j])
129                     addedge(j,30+i,1);
130                 else if(has[j]>1)
131                     addedge(30+i,j,has[j]-1);
132             }
133         }
134         printf("Case #%d: %d\n",kase++,sap(s,t,2+m+n));
135     }
136     return 0;
137 }

 

Similar Posts:

Link of this Article: UVA10779 Collectors Problem

Leave a Reply

Your email address will not be published. Required fields are marked *