原题链接：http://poj.org/problem?id=3207题意：一个圆上，有n个点，标号0到n-1，挑出m对点，连接这m对点，你可以在圆内或圆外连，判断这m条线是否相交？如图：AB和CD两条线，如果之间的连线是红色那两条，那肯定不满足，所以我们可以让BD连在圆外，也就是***那条（当然你也可以让AC连在外面），这样它们就不相交了。遍历所有线，判断这两条线是否是图上的这种关系，也就是若一条线在内，那另一条必须在外，然后建边，接下来很好懂了，直接看代码。#define _CRT_SECURE_NO_DEPRECATE #include&iostream&#include&vector&#include&cstring&#include&queue&#include&stack&#include&algorithm&#define INF struct Node{ int x1, x2;};int n,vector &int& vec[1005];stack&int&Node node[505];int belong[1005];bool inStack[1005];int dfn[1005];int low[1005];void trajan(int u){ low[u] = dfn[u] = ++ inStack[u] = 1; s.push(u); for (int i = 0; i & vec[u].size(); i++) {
int v = vec[u][i];
if (!dfn[v])
trajan(v);
low[u] = min(low[u], low[v]);
else if (inStack[v])
low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) {
p = s.top();
inStack[p] = 0;
belong[p] =
} while (p != u); }}void solve(){ for (int i = 1; i &= 2 * i++)
if (!dfn[i])
trajan(i); for (int i = 1; i & 2 * i = i + 2)//i每次是加2，不是加1 {
if (belong[i] == belong[i + 1])//如果一组点内外线都用那就肯定无解
printf(&the evil panda is lying again/n&);
} } printf(&panda is telling the truth.../n&);}int main(){ scanf(&%d%d&, &n, &m); for (int i = 1; i &= i++) {
scanf(&%d%d&, &node[i].x1, &node[i].x2);
if (node[i].x1 & node[i].x2)
swap(node[i].x1, node[i].x2); } for (int i = 1; i & i++) {
for (int j = i + 1; j &= j++)
if (node[i].x1 &= node[j].x1&&node[i].x2 &= node[j].x1&&node[j].x2 &= node[i].x2 ||
node[j].x1 &= node[i].x1&&node[j].x2 &= node[i].x1&&node[i].x2 &= node[j].x2)
vec[2 * i].push_back(2 * j - 1);//一个在内，一个在外，用奇偶表示
vec[2 * j - 1].push_back(2 * i);
vec[2 * i - 1].push_back(2 * j);
vec[2 * j].push_back(2 * i - 1);
} } solve(); return 0;}
最新教程周点击榜
微信扫一扫