首页 > 代码库 > [luoguP2765] 魔术球问题（最大流—最小不相交路径覆盖）
[luoguP2765] 魔术球问题（最大流—最小不相交路径覆盖）
传送门
枚举球的个数 num
如果 i < j && (i + j) 是完全平方数，那么 i -> j‘ 连一条边
再加一个超级源点 s，s -> i
再加一个超级汇点 t，i‘ -> t
那么当前可以放的柱子的最小数量就是最小不相交路径数
如果当前的最小不相交路径数 > num，break
求最大流的时候别忘了记录方案
——代码
1 #include <cmath> 2 #include <queue> 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #define N 10001 7 #define M 200001 8 #define mid 5000 9 #define min(x, y) ((x) < (y) ? (x) : (y)) 10 11 int n, cnt, sum, ans, s, t = mid << 1; 12 int head[N], to[M], next[M], val[M], suc[N], dis[N]; 13 bool vis[N]; 14 15 inline int read() 16 { 17 int x = 0, f = 1; 18 char ch = getchar(); 19 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 20 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 21 return x * f; 22 } 23 24 inline void add(int x, int y, int z) 25 { 26 to[cnt] = y; 27 val[cnt] = z; 28 next[cnt] = head[x]; 29 head[x] = cnt++; 30 } 31 32 inline bool bfs() 33 { 34 int i, u, v; 35 std::queue <int> q; 36 memset(dis, -1, sizeof(dis)); 37 q.push(s); 38 dis[s] = 0; 39 while(!q.empty()) 40 { 41 u = q.front(), q.pop(); 42 for(i = head[u]; i ^ -1; i = next[i]) 43 { 44 v = to[i]; 45 if(val[i] && dis[v] == -1) 46 { 47 dis[v] = dis[u] + 1; 48 if(v == t) return 1; 49 q.push(v); 50 } 51 } 52 } 53 return 0; 54 } 55 56 inline int dfs(int u, int maxflow) 57 { 58 if(u == t) return maxflow; 59 int i, v, d, ret = 0; 60 for(i = head[u]; i ^ -1; i = next[i]) 61 { 62 v = to[i]; 63 if(val[i] && dis[v] == dis[u] + 1) 64 { 65 d = dfs(v, min(val[i], maxflow)); 66 ret += d; 67 val[i] -= d; 68 val[i ^ 1] += d; 69 if(d) suc[u] = v - mid; 70 if(ret == maxflow) return ret; 71 } 72 } 73 return ret; 74 } 75 76 int main() 77 { 78 int i, j, now, num = 0; 79 n = read(); 80 memset(head, -1, sizeof(head)); 81 while(1) 82 { 83 num++; 84 add(s, num, 1), add(num, s, 0); 85 add(num + mid, t, 1), add(t, num + mid, 0); 86 for(i = 1; i < num; i++) 87 if(sqrt(i + num) == (int)sqrt(i + num)) 88 add(i, num + mid, 1), add(num + mid, i, 0); 89 while(bfs()) sum += dfs(s, 1e9); 90 if(num - sum > n) break; 91 } 92 cnt = 0; 93 memset(head, -1, sizeof(head)); 94 for(i = 1; i < num; i++) 95 { 96 add(s, i, 1), add(i, s, 0); 97 add(i + mid, t, 1), add(t, i + mid, 0); 98 } 99 for(i = 1; i < num; i++)100 for(j = 1; j < i; j++)101 if(sqrt(i + j) == (int)sqrt(i + j))102 add(j, i + mid, 1), add(i + mid, j, 0);103 while(bfs()) dfs(s, 1e9);104 printf("%d\n", num - 1);105 for(i = 1; i < num; i++)106 if(!vis[i])107 {108 now = i;109 while(now)110 {111 printf("%d ", now);112 vis[now] = 1;113 now = suc[now];114 }115 puts("");116 }117 return 0;118 }
[luoguP2765] 魔术球问题（最大流—最小不相交路径覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。