在线推广企业网站的方法,icp网站备案查询,旅游门户网站建设项目招标,河南最新消息活动 - AcWing
在南极附近的某个地方#xff0c;一些企鹅正站在一些浮冰上。
作为群居动物#xff0c;企鹅们喜欢聚在一起#xff0c;因此#xff0c;它们想在同一块浮冰上会合。
企鹅们不想淋湿自己#xff0c;所以它们只能利用自己有限的跳跃能力#xff0c;在一块块…活动 - AcWing
在南极附近的某个地方一些企鹅正站在一些浮冰上。
作为群居动物企鹅们喜欢聚在一起因此它们想在同一块浮冰上会合。
企鹅们不想淋湿自己所以它们只能利用自己有限的跳跃能力在一块块浮冰之间跳跃移动从而聚在一起。
但是最近的温度很高浮冰上也有了裂纹。
每当企鹅在一块浮冰上发力跳到另一块浮冰上时起跳的浮冰都会遭到破坏落点的浮冰并不会因此受到影响。
当浮冰被破坏到一定程度时浮冰就会消失。
现在已知每块浮冰可以承受的具体起跳次数。
请帮助企鹅找出它们可以会合的所有浮冰。 上图是一个浮冰上站着 33 个企鹅的示例图。
输入格式
第一行一个整数 T表示测试数据数量。
对于每组测试数据
第一行包含一个整数 N 和一个浮点数 D表示冰块的数量以及企鹅可以跳跃的最大距离。
接下来 N 行每行包含四个整数 xi,yi,ni,mi用来描述一块浮冰的 X 坐标、Y 坐标、该浮冰上站着的企鹅数量以及该浮冰可以承受的起跳次数。
N 块浮冰按照输入的顺序依次编号为 0∼N−1。
输出格式
对于每组测试数据
输出占一行按从小到大的顺序输出所有可以用来会合的浮冰的编号。
如果无法会合则输出 −1。
数据范围
1≤T≤100, 1≤N≤100, 0≤D≤105, −10000≤xi,yi≤10000 0≤ni≤10 1≤mi≤200
输入样例
2
5 3.5
1 1 1 1
2 3 0 1
3 5 1 1
5 1 1 1
5 4 0 1
3 1.1
-1 0 5 10
0 0 3 9
2 0 1 1输出样例
1 2 4
-1
解析:
拆点将限制流量的点拆成出点入点两点之间用一条边连接。
这样将点的流量转换成边的流量进行控制。
建图方式
建立一个虚拟源点 S连向每个点的每条边的容量点初始的企鹅数量枚举每一个点作为汇点 T。
注意事项
由于是枚举每个点作为汇点 T因此我们不能在上一次的残留网络上直接跑最大流算法必须要还原成初始的残留网络。否则上一次的残留网络中当前的汇点 T 流出的流量将会导致当前图中的流量不守恒。 #includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
#includeunordered_set
#includebitset
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint, int PII;
const int N 210, M 20410 , INF 0x3f3f3f3f;
int n, S, T;
double D;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
PII p[110];
double eps 1e-8;void add(int a, int b, int c) {e[idx] b, f[idx] c, ne[idx] h[a], h[a] idx;e[idx] a, f[idx] 0, ne[idx] h[b], h[b] idx;
}bool check(PII a, PII b) {int x a.first - b.first, y a.second - b.second;return x * x y * y D * D eps;
}bool bfs() {int hh 0, tt 0;memset(d, -1, sizeof d);q[0] S, d[S] 0, cur[S] h[S];while (hh tt) {int t q[hh];for (int i h[t]; i ! -1; i ne[i]) {int j e[i];if (d[j] -1 f[i]) {d[j] d[t] 1;cur[j] h[j];if (j T)return 1;q[tt] j;}}}return 0;
}int find(int u, int limit) {if (u T)return limit;int flow 0;for (int i cur[u]; i ! -1 flow limit; i ne[i]) {int j e[i];cur[u] i;if (d[j] d[u] 1 f[i]) {int t find(j, min(f[i], limit - flow));if (!t)d[j] -1;f[i] - t, f[i ^ 1] t, flow t;}}return flow;
}int dinic() {int ret 0,flow;while (bfs())while (flow find(S, INF))ret flow;//cout ret endl;return ret;
}int main() {int cases 0;cin cases;while (cases--) {memset(h, -1, sizeof h);idx 0;scanf(%d%lf, n, D);S 0;int tot 0;for (int i 1,a,b,c,d; i n; i) {scanf(%d%d%d%d, a, b, c, d);p[i] { a,b };add(S, i, c);add(i, i n, d);tot c;}for (int i 1; i n; i) {for (int j 1; j i; j) {if (check(p[i], p[j])) {add(i n, j, INF);add(j n, i, INF);}}}int cnt 0;for (int i 1; i n; i) {T i;for (int j 0; j idx; j 2) {f[j] f[j ^ 1];f[j ^ 1] 0;}if (dinic() tot) {printf(%d , i - 1);cnt;}}if (!cnt)cout -1 endl;else cout endl;}return 0;
}
