P4659 阀门题解

0nullptr · 2019-10-14 16:34:36 · 题解

题目传送门：P4659 BalticOI 2008阀门

这道题要求我们找到一种排列方式，使得两个水池不相互连通。其中每个阀门有开关两种状态。

很容易想到直接暴力枚举每个开关的开闭状态，判断每种状态是否可行，但这样只能过30%的数据。

考虑将每个开关的开闭关系抽象成一个点，并以水管的开放与否作为边的连接条件，那么我们可以推断出这样一个结论：对于一个开关，如果在图中的一个强联通分量中出现它既开又关的情况 ~~（薛定谔：不是我干的）~~ ，那么一定是无解情况，而且当且仅当出现这种情况时无解。

根据以上结论，可以找到这种建图方式：

将每个开关\text{i}拆成两个点，正点\text{i << 1}和反点\text{i << 1 | 1}，分别表示开关在开\闭情况下这个管道的开放情况。
对于每行输入给定的两个点，我们从一个点向另一个点的反点建立单向边，表示当一个开关开\闭时，另一个开关的状态

在如上建图并求出图的强连通分量之后，就只需要找出一种使不同强连通分量之间的点不互相影响的做法。有一种简单的方法是判断一个开关的正反点所处的强连通分量编号值，正点大的为断开，反点大的为闭合。

附上完整代码

vector<int> G[MAXN];
int pre[MAXN], lowlink[MAXN], sccno[MAXN];
stack<int> S;
int dfs_clock, scc_cnt;//强连通分量系变量声明

//朴素的强连通分量板子
void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for (unsigned i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!pre[v]) {
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        } else if (!sccno[v]) {
            lowlink[u] = min(lowlink[u], pre[v]);
        }
    }
    if (lowlink[u] == pre[u]) {
        scc_cnt++;
        while(1) {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if(x == u) break;
        }
    }
}

void find_scc(int n) {
    for (int i = 2 ; i <= n; i++)
        if(!pre[i]) dfs(i);
}

int main() {
    int n, m;
    cin>>n>>m;
    for (int i = 1; i <= n; i++) {
        int u, tu, v, tv;
        cin>>u>>tu>>v>>tv;
        int x = 2 * u + tu, y = 2 * v + tv;
        G[x].push_back(y ^ 1);
        G[y].push_back(x ^ 1);
    }//存图
    find_scc(m * 2 + 1);
    queue<int> ans;//用于记录答案
    for (int i = 1; i <= m; i++) {
        if (sccno[i << 1] > sccno[i << 1 | 1])
            ans.push(0);
        else if (sccno[i << 1] == sccno[i << 1 | 1]) {
            puts("IMPOSSIBLE");
            return 0;//判断无解情况，及时退出
        } else ans.push(1);
    }
    while (!ans.empty()) cout<<ans.front()<<endl, ans.pop();//输出答案
    return 0;
}

P4659 阀门 题解

P4659 阀门题解