首页 > 代码库 > zoj 3642 Just Another Information Sharing Problem【最大流||多重匹配】
zoj 3642 Just Another Information Sharing Problem【最大流||多重匹配】
大意：
有n个熊孩子，，每个熊孩子有a个秘密，他最少愿意分享b个秘密， 最多愿意分享c个秘密， 接下来a个数表示这个熊孩子有的a个秘密的id
最后给一个熊孩子的编号m， 询问编号m最多能够知道多少个秘密
分析：
最大流， 但是询问的那个孩子的秘密就不用封印了，哈哈
也可以用二分图多重匹配， 而且时间快了一倍
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <queue> 6 #include <map> 7 using namespace std; 8 9 const int maxn = 500 * 250 + 10; 10 const int INF = 1000000000; 11 12 struct Edge { 13 int from, to, cap, flow; 14 }; 15 16 struct Dinic { 17 int n, m, s, t; 18 vector<Edge> edges; 19 vector<int>G[maxn]; 20 bool vis[maxn]; 21 int d[maxn]; 22 int cur[maxn]; 23 24 void ClearAll(int n) { 25 for(int i = 0; i <= n; i++) { 26 G[i].clear(); 27 } 28 edges.clear(); 29 } 30 31 void AddEdge(int from, int to, int cap) { 32 edges.push_back((Edge) { from, to, cap, 0 } ); 33 edges.push_back((Edge) { to, from, 0, 0 } ); 34 m = edges.size(); 35 G[from].push_back(m - 2); 36 G[to].push_back(m - 1); 37 } 38 39 bool BFS() 40 { 41 memset(vis, 0, sizeof(vis) ); 42 queue<int> Q; 43 Q.push(s); 44 vis[s] = 1; 45 d[s] = 0; 46 while(!Q.empty() ){ 47 int x = Q.front(); Q.pop(); 48 for(int i = 0; i < G[x].size(); i++) { 49 Edge& e = edges[G[x][i]]; 50 if(!vis[e.to] && e.cap > e.flow) { 51 vis[e.to] = 1; 52 d[e.to] = d[x] + 1; 53 Q.push(e.to); 54 } 55 } 56 } 57 return vis[t]; 58 } 59 60 int DFS(int x, int a) { 61 if(x == t || a == 0) return a; 62 int flow = 0, f; 63 for(int& i = cur[x]; i < G[x].size(); i++) { 64 Edge& e = edges[G[x][i]]; 65 if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { 66 e.flow += f; 67 edges[G[x][i]^1].flow -= f; 68 flow += f; 69 a -= f; 70 if(a == 0) break; 71 } 72 } 73 return flow; 74 } 75 76 int MaxFlow(int s, int t) { 77 this -> s = s; this -> t = t; 78 int flow = 0; 79 while(BFS()) { 80 memset(cur, 0, sizeof(cur)); 81 flow += DFS(s, INF); 82 } 83 return flow; 84 } 85 }; 86 87 Dinic g; 88 89 map<int, int> mp; 90 int a[maxn], b[maxn], c[maxn]; 91 int A[55][205]; 92 93 int n, m, num, tot; 94 int s, t; 95 96 int main() { 97 while(EOF != scanf("%d",&n) ) { 98 for(int i = 1; i <= n; i++) { 99 scanf("%d %d %d",&a[i], &b[i], &c[i]);100 for(int j = 1; j <= a[i]; j++) {101 scanf("%d",&A[i][j]);102 }103 }104 scanf("%d",&m);105 mp.clear();106 g.ClearAll(n * (n + 200) );107 s = 0; t = n + 200 + 1;108 int tot = n + 1;109 for(int i = 1; i <= n; i++) {110 if(i != m) {111 g.AddEdge(s, i, c[i]);112 } else {113 g.AddEdge(s, i, a[i]);114 }115 for(int j = 1; j <= a[i]; j++) {116 num = A[i][j];117 if(!mp[num]) mp[num] = tot++;118 g.AddEdge(i, mp[num], 1);119 }120 }121 for(int i = n + 1; i < tot; i++) {122 g.AddEdge(i, t, 1);123 }124 printf("%d\n", g.MaxFlow(s, t));125 }126 return 0;127 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <map> 6 using namespace std; 7 8 const int maxn = 205; 9 10 int cap[maxn];11 int Link[maxn][maxn];12 int vLink[maxn];13 int mat[maxn][maxn];14 int vis[maxn];15 int n, m;16 17 bool Find(int u) {18 for(int i = 1; i <= m; i++) {19 if(!vis[i] && mat[u][i]) {20 int v = i;21 vis[v] = 1;22 if(vLink[v] < cap[v]) {23 Link[v][vLink[v]++] = u;24 return true;25 }26 for(int j = 0; j < vLink[v]; j++) {27 if(Find(Link[v][j])) {28 Link[v][j] = u;29 return true;30 }31 }32 }33 }34 return false;35 }36 37 int solve() {38 int cnt = 0;39 memset(Link, 0, sizeof(Link));40 memset(vLink, 0, sizeof(vLink));41 for(int i = 1; i <= n; i++) {42 memset(vis, 0, sizeof(vis));43 if(Find(i) ) cnt ++;44 }45 return cnt;46 }47 48 int a[maxn], b[maxn], c[maxn];49 int A[maxn][maxn];50 map<int, int> mp;51 52 int main() {53 int x, y;54 while(EOF != scanf("%d",&x) ) {55 for(int i = 1; i <= x; i++) {56 scanf("%d %d %d", &a[i], &b[i], &c[i]);57 for(int j = 1; j <= a[i]; j++) {58 scanf("%d",&A[i][j]);59 }60 }61 scanf("%d",&y);62 mp.clear();63 memset(mat, 0, sizeof(mat));64 int tot = 1;65 for(int i = 1; i <= x; i++) {66 cap[i] = c[i];67 for(int j = 1; j <= a[i]; j++) {68 int num = A[i][j];69 if(!mp[num]) mp[num] = tot++;70 mat[mp[num]][i] = 1;71 }72 }73 cap[y] = a[y];74 n = tot - 1; m = x;75 printf("%d\n", solve());76 }77 return 0;78 }
zoj 3642 Just Another Information Sharing Problem【最大流||多重匹配】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。