当前位置：首页 > news >正文

C-Cleaning Pipes(判断两线段相交+二分图判定) 2015-2016 Northwestern European Regional Contest (NWERC 2015)

news 来源：原创 2024/5/5 22:35:40

题意：

给定w个井口和p条管道，管道相交即代表有交点，现派出机器人进入若干管道进行清理交点，相交的管道之间最多允许存在一个机器人，问能否派出机器人将所有节点进行清理，且满足限制。

思路：

将管道抽象成点，如果管道之间存在交点则进行连边，所以问题就转化为了寻找一些点覆盖所有边且这些点之间不存在连边。从而问题就再次变成了判断连通图是否为二分图。

代码1(利用并差集判定二分图)：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct P {  
    int x, y;  
    P(int _x = 0, int _y = 0) : x(_x), y(_y) {}  
    bool operator == (P &b)  
    {  
        return x == b.x && y == b.y;  
    }  
} tmp[maxn], L[maxn], R[maxn];
//计算向量p1p2与向量p1p3的叉积，若p1p3在p1p2的逆时针方向，则返回>0，顺时针方向返回<0  
int mul(P p1, P p2, P p3)  
{  
    return (p2.x-p1.x) * (p3.y-p1.y) - (p3.x-p1.x) * (p2.y-p1.y);  
}  
bool intersect(P p1, P p2, P q1, P q2)  //利用线段1的两端点和线段2的两端点判断线段12是否相交
{  
	//快速排斥  
    if(max(p1.x,p2.x) < min(q1.x,q2.x)||  
       max(q1.x,q2.x) < min(p1.x,p2.x)||  
       max(p1.y,p2.y) < min(q1.y,q2.y)||  
       max(q1.y,q2.y) < min(p1.y,p2.y))  
    return 0;  
	//跨立试验  
    if(1ll*mul(p1,p2,q1)*mul(p1,p2,q2) <= 0 && 1ll*mul(q1,q2,p1)*mul(q1,q2,p2) <= 0)  
    return 1;  
    return 0;
}

int f[maxn*2];
int w, p;
int getf(int x){return x == f[x]? x: f[x] = getf(f[x]);}
void merge(int a, int b)
{
	int fa = getf(a), fb = getf(b);
	if(fa != fb) f[fb] = fa;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	scanf("%d %d", &w, &p);
	for(int i = 1; i <= w; ++i)
	scanf("%d %d", &tmp[i].x, &tmp[i].y);
	for(int i = 1; i <= p; ++i)
	{
		int t;
		scanf("%d %d %d", &t, &R[i].x, &R[i].y);
		L[i] = tmp[t];
	}
	for(int i = 1; i <= 2*p; ++i) f[i] = i;
	for(int i = 1; i <= p; ++i)
	for(int j = i+1; j <= p; ++j)
	{
		if(L[i] == L[j]) continue;
		if(intersect(L[i], R[i], L[j], R[j]))
		{
			//如果有连边就将i,j+n归为一个集合，j,i+n归为一个集合 
			merge(i, j+p);
			merge(j, i+p);
		}
	}
	bool flag = true;
	for(int i = 1; i <= p; ++i)
	if(getf(i) == getf(i+p))
	//如果i和i+n属于同一个集合，则说明有奇环存在。
	{
		flag = false;
		break;
	}
	if(flag) puts("possible");
	else puts("impossible");
	return 0;
}

代码2(经典染色法判定二分图)：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct P {  
    int x, y;  
    P(int _x = 0, int _y = 0) : x(_x), y(_y) {}  
    bool operator == (P &b)  
    {  
        return x == b.x && y == b.y;  
    }  
} tmp[maxn], L[maxn], R[maxn];
//计算向量p1p2与向量p1p3的叉积，若p1p3在p1p2的逆时针方向，则返回>0，顺时针方向返回<0  
int mul(P p1, P p2, P p3)  
{  
    return (p2.x-p1.x) * (p3.y-p1.y) - (p3.x-p1.x) * (p2.y-p1.y);  
}  
bool intersect(P p1, P p2, P q1, P q2)  //利用线段1的两端点和线段2的两端点判断线段12是否相交
{  
	//快速排斥  
    if(max(p1.x,p2.x) < min(q1.x,q2.x)||  
       max(q1.x,q2.x) < min(p1.x,p2.x)||  
       max(p1.y,p2.y) < min(q1.y,q2.y)||  
       max(q1.y,q2.y) < min(p1.y,p2.y))  
    return 0;  
	//跨立试验  
    if(1ll*mul(p1,p2,q1)*mul(p1,p2,q2) <= 0 && 1ll*mul(q1,q2,p1)*mul(q1,q2,p2) <= 0)  
    return 1;  
    return 0;
}

int col[maxn];
int w, p;
vector<int> g[maxn];
bool dfs(int u, int key)
{
	col[u] = key;
	for(int i = 0; i < g[u].size(); ++i)
	{
		int v = g[u][i];
		if(col[v] == key) return false;
		if(col[v] != -1) continue;
		if(!dfs(v, key^1)) return false;
	}
	return true;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	scanf("%d %d", &w, &p);
	for(int i = 1; i <= w; ++i)
	scanf("%d %d", &tmp[i].x, &tmp[i].y);
	for(int i = 1; i <= p; ++i)
	{
		int t;
		scanf("%d %d %d", &t, &R[i].x, &R[i].y);
		L[i] = tmp[t];
		g[i].clear();
	}
	for(int i = 1; i <= p; ++i)
	for(int j = i+1; j <= p; ++j)
	{
		if(L[i] == L[j]) continue;
		if(intersect(L[i], R[i], L[j], R[j]))
		{
			g[i].push_back(j);
			g[j].push_back(i);
		}
	}
	memset(col, -1, sizeof col);
	bool flag = true;
	for(int i = 1; i <= p; ++i)
	if(col[i] == -1 && !dfs(i, 0))
	{
		flag = false;
		break;
	}
	if(flag) puts("possible");
	else puts("impossible");
	return 0;
}

继续加油~