题意简述
给定一张无向图,每条边有个哨兵,初始在边的中间。你可以把某个结点旁边的哨兵全部吸引或远离这个结点。给出最后每个哨兵在边的哪一端,请构造出一种可能的操作方案或报告无解。多种情况输出任意解,你不需要最小化操作步数。
题目分析
发现一个哨兵和且仅和最后一次关联这条边的操作有关,考虑使用“浮水法”反转操作,即假定一个哨兵在被定向后就不会再发生变化,那么把这样的方案倒序输出就是原问题答案了。
那么如何求解这个问题呢?发现一开始操作的点一定是哨兵最终要全部靠近或远离这个点的,为简化讨论,不妨令一开始操作的点连出的所有边,哨兵都在这个点一侧。那么给它设为吸引哨兵后,它对其他节点就没有了影响。所以考虑删去这个点和其连出的边,循环此过程。
发现这就是在跑一个拓扑排序。既然是拓扑排序,无解的时候当且仅当出现了环,也就是最后还有的边不能被确定。
于是这道水题就愉快地过掉啦。
代码(已略去快读快写)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include <iostream>
#include <cstdio>
#define debug(a) cerr << "Line: " << __LINE__ << " " << #a << endl
#define print(a) cerr << #a << "=" << (a) << endl
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define main Main(); signed main(){ return ios::sync_with_stdio(0), cin.tie(0), Main(); } signed Main
using namespace std;
int n, m;
struct Graph{
struct node{
int to, nxt;
} edge[500010 << 1];
int eid, head[500010];
inline void add(int u, int v){
edge[++eid] = {v, head[u]};
head[u] = eid;
}
inline node & operator [] (const int x){
return edge[x];
}
} xym;
int du[500010], Q[500010], top;
int ans[500010], tot;
signed main(){
read(n, m);
for (int i = 1, u, v; i <= m; ++i) read(u, v), xym.add(u, v), ++du[v];
for (int i = 1; i <= n; ++i) !du[i] && (Q[++top] = i);
while (top){
int now = Q[top--]; ans[++tot] = now; // 给这个点设为吸引哨兵
for (int i = xym.head[now]; i; i = xym[i].nxt)
if (!--du[xym[i].to]) Q[++top] = xym[i].to; // 拓扑排序
}
for (int i = 1; i <= n; ++i) du[i] && (write(-1), exit(0), yzh_i_love_you);
// 无解当且仅当最后出现了环
write(tot, '\n');
for (int i = tot; i >= 1; --i) write(ans[i], ' ', 1, '\n'); // 逆序输出
return 0;
}
总结 & 后话
对于这种最终结果依赖于最后一次操作的时候,考虑使用“浮水法”,反转操作顺序,它被操作后就不再变化了,而实际操作顺序就是新操作顺序的逆序。
标签:GCC,COCI2021,洛谷,题解,哨兵,pragma,操作,逆序 From: https://www.cnblogs.com/XuYueming/p/18107392