题意
有n个点按顺序排列在一个圆上,编号依次为0~n-1,在n点之间有m条边,这些边可以在圆内连接两点,也可以在圆外连接两点(如下图所示),问是否存在一种连接法,使得m条边不相交。
解题思路
我们发现对于每条边,只存在两种状态:圆内、圆外,而且某些边之间存在矛盾关系,显然,这是一个2-sat问题,我们记a表示圆内的边,¬a表示圆外的边
由于输入只给出了某两点之间存在的边,而没有给出边的矛盾关系,那么我们需要将所有边存储下来,随后处理出边之间的矛盾关系。
如上图所示右边的两条边,发现如果某两条在内部的边相交,那么对应的在外部边也相交,所以对于冲突的两边a,b,必满足 a → ¬b Λ b → ¬a,表示a,b不同时出现在圆内和圆外
而对于两条在内部的边不相交,其对应的在外部的边也不交,同时一条在内,一条在外的边也不相交,说明不存在矛盾关系,无需处理
总结:我们先记录下所有的边,用i表示位于内部的边,用i+n表示其对应的位于外部的边,随后用m^2的复杂度枚举每条边和其余边,判断是否存在矛盾关系,如果两条边在内部或者外部相交,那么必定满足a → ¬b Λ b → ¬a,所以我们在a和b+n,b和a+n之间分别建一条无向边,然后我们用tarjan在图中求出强连通分量SCC,最后枚举每条边x,判断x和¬x是否处于同一强连通分量,如果每条边的内部和外部的边都不在同一强连通分量中,那么就是正确的,反之错误
代码区
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<string> #include<fstream> #include<vector> #include<stack> #include <map> #include <iomanip> #define bug cout << "**********" << endl #define show(x, y) cout<<"["<<x<<","<<y<<"] " #define LOCAL = 1; using namespace std; typedef long long ll; const ll inf = 2e9 + 10; const ll mod = 1e9 + 7; const int Max = 1e4 + 10; const int Max2 = 3e2 + 10; int n, m; vector<int> edge[Max]; pair<int, int> way[Max]; //存边 int dfn[Max],low[Max],time_clock; int id[Max],sccCnt; int line[Max],now; void init() { for(int i = 0;i < Max; i ++) edge[i].clear(); memset(dfn,0,sizeof(dfn)); time_clock = 0; sccCnt = 0; memset(id,0,sizeof(id)); now = 0; } void tarjan(int u) { dfn[u] = low[u] = ++time_clock; line[++now] = u; for(vector<int>::iterator it = edge[u].begin(); it != edge[u].end();++it) { int v = *it; if(!dfn[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if(!id[v]) { low[u] = min(low[u],dfn[v]); } } if(dfn[u] == low[u]) { sccCnt++; while(line[now] != u) id[line[now--]] = sccCnt; id[line[now--]] = sccCnt; } } int main() { #ifdef LOCAL //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif while (scanf("%d%d", &n, &m) != EOF) { init(); for (int i = 1, u, v; i <= m; i++) { scanf("%d%d", &u, &v); if (u > v) swap(u, v); //方便起见,处理一下 way[i].first = u; way[i].second = v; } for (int i = 1; i <= m; i++) { for (int j = i + 1; j <= m; j++) { int num =0; if(way[i].first < way[j].first && way[j].first < way[i].second) num++; if(way[i].first < way[j].second && way[j].second < way[i].second) num++; if(num == 1) //两边冲突,只有一边内一边外才合法 { edge[i].push_back(j+m); edge[j+m].push_back(i); //i在内,j在外 edge[j].push_back(i+m); edge[i+m].push_back(j); //i在外,j在内 } } } for(int i = 1;i <= (m<<1);i ++) { if(!dfn[i]) tarjan(i); } bool ok = true; for(int i = 1;i <= m ;i ++) { if(id[i] == id[i+m]) //处于同一强连通分量中,说明无解 { ok = false; break; } } if(ok) printf("panda is telling the truth...\n"); else printf("the evil panda is lying again\n"); } return 0; }View Code