[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 23 24 inline void add(int x, int y, int z) 25 31 32 inline bool bfs() 33 51 } 52 } 53 return 0; 54 } 55 56 inline int dfs(int u, int maxflow) 57 72 } 73 return ret; 74 } 75 76 int main() 77 92 cnt = 0; 93 memset(head, 1, sizeof(head)); 94 for(i = 1; i < num; i++) 95 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 115 puts(""); 116 } 117 return 0; 118 }
View Code

上一篇：[luoguP2764] 最小路径覆盖问题（最大流 || 二分图最大匹配）

下一篇：[luoguP2766] 最长递增子序列问题（最大流）

---

最大流 网络流 最小路径覆盖