ZOJ 3642 多重匹配离散化.cpp

题意：

已知一些小孩所拥有的信息和他最多共享信息量和最少共享信息量问其中某一个小孩最多得到的信息量

给出n表示有n个小孩

接下来n行有 a b c a1 a2 a3 a4 ... ai 表示该小孩有信息a条最少共享 b 条最多共享 c 条其中a1 a2 a3~ai为小孩拥有信息id号

给出一个m 问的是小孩m最多得到的信息量

思路：

鉴于这道题中信息id号从 0 ~ 200 但是每个小孩最初最多知道10条信息..

所以为了防止遍历的时候太浪费时间应该把题目id号变成连续的..

然后可以用多重匹配或者最大流来做..

Tips：

多重匹配的建图方法：

以信息为集合X 孩子为集合Y

然后 limit 为 Y 集合的最大容量即孩子的最大共享量但是孩子 m 的容量为INF

最大流的建图方法：

一个超级源点..连接孩子除了第m个孩子之外..

别的孩子都连线..容量为最大分享量..而第m个孩子的容量为INF 表示可以接受无穷多的信息

然后每个孩子和对应的信息连线容量为1

每个信息又与超级汇点连线容量为1

求超级源点到超级汇点的最大流既是答案

Code：

最大流

  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 #define clr(x) memset(x, 0xff, sizeof(x))
  6 #define min(a,b)(a)<(b)?(a):(b)
  7 
  8 const int INF = 0x1f1f1f1f;
  9 const int maxn = 410;
 10 const int maxm = 200010;
 11 
 12 struct Info
 13 {
 14     int m;
 15     int id[210];
 16     int cap;
 17 }info[210];
 18 
 19 struct Edge
 20 {
 21     int from;
 22     int to;
 23     int next;
 24     int w;
 25 }edge[maxm];
 26 int tot;
 27 int head[maxn];
 28 
 29 int num[1000010];
 30 
 31 void add(int s, int u, int f1, int f2)
 32 {
 33     edge[tot].from = s;
 34     edge[tot].to = u;
 35     edge[tot].w = f1;
 36     edge[tot].next = head[s];
 37     head[s] = tot++;
 38     edge[tot].from = u;
 39     edge[tot].to = s;
 40     edge[tot].w = f2;
 41     edge[tot].next = head[u];
 42     head[u] = tot++;
 43 }
 44 
 45 int q[maxn];
 46 int cnt[maxn];
 47 int d[maxn];
 48 int low[maxn];
 49 int cur[maxn];
 50 
 51 int maxflow(int s, int t, int n)
 52 {
 53     int *front = q, *rear = q;
 54     for(int i = 0; i <= n; ++i) {
 55         d[i] = n;
 56         cnt[i] = 0;
 57     }
 58     cnt[n] = n-1;
 59     cnt[0]++;
 60     d[t] = 0;
 61     *rear++ = t;
 62     while(front < rear) {
 63         int v = *front++;
 64         for(int i = head[v]; i != -1; i = edge[i].next) {
 65             if(d[edge[i].to] == n && edge[i^1].w > 0) {
 66                 d[edge[i].to] = d[v] + 1;
 67                 cnt[n]--;
 68                 cnt[d[edge[i].to]]++;
 69                 *rear++ = edge[i].to;
 70             }
 71         }
 72     }
 73 
 74     int flow = 0, u = s, top = 0;
 75     low[0] = INF;
 76     for(int i = 0; i <= n; ++i) {
 77         cur[i] = head[i];
 78     }
 79     while(d[s] < n) {
 80         int &i = cur[u];
 81         for(; i != -1; i = edge[i].next) {
 82             if(edge[i].w > 0 && d[u] == d[edge[i].to]+1) {
 83                 low[top+1] = min(low[top], edge[i].w);
 84                 q[++top] = i;
 85                 u = edge[i].to;
 86                 break;
 87             }
 88         }
 89         if(i != -1) {
 90             if(u == t) {
 91                 int minf = low[top];
 92                 for(int p = 1, i; p <= top; ++p) {
 93                     i = q[p];
 94                     edge[i].w -= minf;
 95                     edge[i^1].w += minf;
 96                 }
 97                 flow += minf;
 98                 u = s;
 99                 low[0] = INF;
100                 top = 0;
101             }
102         }
103         else {
104             int old_du = d[u];
105             cnt[old_du]--;
106             d[u] = n-1;
107             for(int i = head[u]; i != -1; i = edge[i].next)
108                 if(edge[i].w > 0 && d[u] > d[edge[i].to]) {
109                     d[u] = d[edge[i].to];
110                 }
111                 cnt[++d[u]]++;
112                 if(d[u]<n)
113                     cur[u] = head[u];
114                 if(u != s) {
115                     u = edge[q[top]].from;
116                     --top;
117                 }
118                 if(cnt[old_du] == 0) break;
119         }
120     }
121     return flow;
122 }
123 
124 int main()
125 {
126     int i, j, k;
127     int n, tmp, tt, m;
128     while(scanf("%d", &n) != EOF)
129     {
130         clr(head), tot = 0, tt = n+1;
131         memset(num, 0, sizeof(num));
132 
133         for(i = 1; i <= n; ++i) {
134             scanf("%d%*d%d", &info[i].m, &info[i].cap);
135             for(j = 0; j < info[i].m; ++j){
136                 scanf("%d", &tmp);
137                 if(num[tmp] == 0) num[tmp] = tt++;
138                 info[i].id[j] = num[tmp];
139             }
140         }
141 
142         scanf("%d", &m);
143 
144         for(i = 1; i <= n; ++i) {
145             if(i != m)
146                 add(0, i, info[i].cap, 0);
147             else
148                 add(0, i, INF, 0);
149             for(j = 0; j < info[i].m; ++j)
150                 add(i, info[i].id[j], 1, 0);
151         }
152 
153         for(i = n+1; i < tt; ++i)
154         add(i, tt, 1, 0);
155 
156         int ans = maxflow(0, tt, tt+1);
157 
158         printf("%d\n", ans);
159     }
160     return 0;
161 }

多重匹配

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define clr(x) memset(x, 0, sizeof(x))
 6 const int INF = 0x1f1f1f1f;
 7 
 8 bool G[410][210];
 9 int limit[410];
10 bool vis[410];
11 int v1, v2, sum;
12 int v[410];
13 int vv[210][410];
14 int num[1000010];
15 
16 bool find(int u)
17 {
18     int i, j, k;
19     for(i = 0; i < v2; ++i) {
20         if(G[u][i] && !vis[i]) {
21             vis[i] = true;
22             if(v[i] < limit[i]) {
23                 vv[i][v[i]++] = u;
24                 return true;
25             }
26 
27             for(j = 0; j < v[i]; ++j) {
28                 if(find(vv[i][j])) {
29                     vv[i][j] = u;
30                     return true;
31                 }
32             }
33         }
34     }
35     return false;
36 }
37 
38 void solve()
39 {
40     clr(vis);
41     sum = 0;
42     for(int i = 1; i <= v1; ++i) {
43         clr(vis);
44         if(find(i)) {
45             sum++;
46         }
47     }
48 }
49 
50 int main()
51 {
52     int i, j, k;
53     int n, m, tmp, tt;
54     while(scanf("%d", &n) != EOF)
55     {
56         clr(G), clr(num);
57         tt = 1;
58 
59         for(i = 0; i < n; ++i) {
60             scanf("%d%*d%d", &m, &limit[i]);
61             while(m--) {
62                 scanf("%d", &tmp);
63                 if(num[tmp] == 0) num[tmp] = tt++;
64                 G[num[tmp]][i] = true;
65             }
66         }
67 
68         v1 = tt-1;
69         v2 = n;
70         scanf("%d", &m);
71 
72         limit[m-1] = INF;
73         solve();
74 
75         printf("%d\n", sum);
76     }
77     return 0;
78 }

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4810

ZOJ 3642 多重匹配 离散化.cpp

ZOJ 3642 多重匹配离散化.cpp