POJ2723 题解

WA了半天才发现居然是因为没看见这道题有多组数据，wzfl。。。

题目大意：有N对钥匙，对于每一对钥匙，如果使用了其中一把，另一把钥匙就会消失。接下来有M扇门，每扇门上有两把锁，分别对应两把钥匙（锁会重复出现，每把钥匙也可以重复使用），打开其中任意一把就可以打开这扇门，再打开第m扇门后才可以去尝试打开第m+1扇门。问最多能打开多少扇门。

思路：每个钥匙都有使用与不使用两种状态且必须是其中一种状态，于是想到2-SAT，对于配对的钥匙a，b，使用了一个之后另一个就不能使用，所以在图中连边（a，¬b）和（b，¬a）。

对于每个门上的两个钥匙c，d，如果门能打开，就一定有一个钥匙被使用，所以如果不用其中一个，就必须用另外一个，所以在图中连边（¬c，d）和（¬d，c）。

由于必须从第一扇们门开始向后连续尝试开门，接下来通过二分就能找到可以打开的最大门数，对于每个门数e，处理前e个门的钥匙，如果该2-SAT有解，就说明可以打开e扇门，否则不行。

代码如下：

//POJ.2723

//Author: Prgl

#include<bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef long long ll;

typedef vector<int>vec;

#define INF 0x3f3f3f3f

const int maxv = 1 << 14;

const int maxd = 1 << 15;

int V;

vec G[maxv], rG[maxv];

stack<int>s;

bool used[maxv];

int cmp[maxv];

inline void add_edge(int from, int to)

{

	G[from].push_back(to);

	rG[to].push_back(from);

}

void dfs(int v)

{

	used[v] = true;

	for (int i = 0; i < G[v].size(); i++)

	{

		if (!used[G[v][i]])

			dfs(G[v][i]);

	}

	s.push(v);

}

void rdfs(int v, int k)

{

	cmp[v] = k;

	used[v] = true;

	for (int i = 0; i < rG[v].size(); i++)

	{

		if (!used[rG[v][i]])

			rdfs(rG[v][i], k);

	}

}

int scc()

{

	memset(used, 0, sizeof(used));

	for (int v = 0; v < V; v++)

	{

		if (!used[v])

			dfs(v);

	}

	memset(used, 0, sizeof(used));

	int k = 0;

	while (!s.empty())

	{

		int v = s.top();

		s.pop();

		if (!used[v])

			rdfs(v, k++);

	}

	return k;

}

int N, M, K;

int a[maxv], b[maxv];

int A[maxd], B[maxd];

bool C(int d)

{

	for (int v = 0; v < V; v++)

	{

		G[v].clear();

		rG[v].clear();

	}

	for (int i = 0; i < N; i++)

	{

		add_edge(a[i], b[i] + K);

		add_edge(b[i], a[i] + K);

	}

	for (int i = 0; i < d; i++)

	{

		add_edge(B[i] + K, A[i]);

		add_edge(A[i] + K, B[i]);

	}

	memset(cmp, 0, sizeof(cmp));

	scc();

	for (int i = 0; i < K; i++)

	{

		if (cmp[i] == cmp[i + K])

			return false;

	}

	return true;

}

void solve()

{

	K = N * 2;

	V = N * 4;

	int lo = 0, hi = M + 1;

	while (hi - lo > 1)

	{

		int mi = (lo + hi) / 2;

		if (C(mi))

			lo = mi;

		else

			hi = mi;

	}

	cout << lo << endl;

}

int main()

{

	IOS;

	cin >> N >> M;

	while (N != 0 || M != 0)

	{

		for (int i = 0; i < N; i++)

			cin >> a[i] >> b[i];

		for (int i = 0; i < M; i++)

			cin >> A[i] >> B[i];

		solve();

		cin >> N >> M;

	}

	return 0;

}

巴特西

POJ2723 题解

最新文章

热门文章