社区讨论
一点小疑惑
P1500[集训队互测 2000] 丘比特的烦恼参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @loqxrbww
- 此快照首次捕获于
- 2023/11/09 16:37 2 年前
- 此快照最后确认于
- 2023/11/09 19:18 2 年前
我建好了边,可是应该怎么改变Dinic才行啊。
Dinic:
CPPinline int dfs(int x, LL sumflow){
if (x == t) return sumflow;
LL res, ret = 0;
for (int i = temp[x]; i && sumflow; i = Next[i]){
temp[x] = i;
if (w[i] > 0 && (d[ver[i]] == d[x] + 1)){
res = dfs(ver[i], min(sumflow, w[i]));
if (!res) d[ver[i]] = INF;
w[i] -= res;
w[i ^ 1] += res;
ret += res;
sumflow -= res;
}
}
return ret;
}
建边:
CPPstring name1, name2;
cin >> name1;
while (name1 != "End"){
cin >> name2;cin >> ww;
deals(name1);deals(name2);
int xx = mp[name1].first, xy = mp[name1].second, yx = mp[name2].first, yy = mp[name2].second;
if ((xx - yx) * (xx - yx) + (xy - yy) * (xy - yy) <= k * k){
int man = hax[name1], woman = hax[name2];
if (man > woman) swap(man, woman);
add(man, woman, 1);add(woman, man, -ww);
love[man][woman] = ww;
}
cin >> name1;
}
for (int i = 1; i <= n; i++){
for (int j = n + 1; j <= n * 2; j++){
if (!love[i][j]){
int xx = mp[name[i]].first, xy = mp[name[i]].second, yx = mp[name[j]].first, yy = mp[name[j]].second;
if ((xx - yx) * (xx - yx) + (xy - yy) * (xy - yy) <= k * k)
add(i, j, 1), add(j, i, -1);
love[i][j] = 1;
}
}
}
s = n * 2 + 1;t = n * 2 + 2;
for (int i = 1; i <= n; i++) add(s, i, 1), add(i, s, 0);
for (int i = n + 1; i <= n * 2; i++) add(i, t, 1), add(t, i, 0);
while (bfs()) {ans += dfs(s, INF);}
其中 表示这个名字是第几个人, 表示该名字的坐标。
回复
共 1 条回复,欢迎继续交流。
正在加载回复...