社区讨论

一点小疑惑

P1500[集训队互测 2000] 丘比特的烦恼参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@loqxrbww
此快照首次捕获于
2023/11/09 16:37
2 年前
此快照最后确认于
2023/11/09 19:18
2 年前
查看原帖
我建好了边,可是应该怎么改变Dinic才行啊。 Dinic:
CPP
inline 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;
}
建边:
CPP
string 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);}
其中 haxhax 表示这个名字是第几个人,mpmp 表示该名字的坐标。

回复

1 条回复,欢迎继续交流。

正在加载回复...