「BZOJ1997」[HNOI2010] Planar
Description
Input
Output
题解
用平面图m<=3n-6的性质剪枝条
若两条边在圆内相交，则他们在圆外也是相交的，即若a,b不能同时取，a’,b’也不能同时取
按2-sat建模缩点后判断合法性
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define rad 100000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m,ind,top,cnt,scc; int u[10005],v[10005]; int c[2005],pos[2005]; int last[2005],dfn[2005],low[2005],q[2005],bl[2005]; bool inq[2005]; struct edge{ int to,next; }e[1000005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } void tarjan(int x) { inq[x]=1;q[++top]=x; low[x]=dfn[x]=++ind; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); else if(inq[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); int now=-1; if(low[x]==dfn[x]) { scc++; while(now!=x) { now=q[top--];inq[now]=0; bl[now]=scc; } } } bool jud() { for(int i=1;i<=m;i++) if(bl[2*i]==bl[2*i-1])return 0; return 1; } int main() { T=read(); while(T--) { n=read();m=read(); for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(); memset(last,0,sizeof(last));cnt=0; scc=ind=0; memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); for(int i=1;i<=n;i++)c[i]=read(); if(m>3*n-6){puts("NO");continue;} for(int i=1;i<=n;i++)pos[c[i]]=i; top=0; for(int i=1;i<=m;i++) { v[i]=pos[v[i]];u[i]=pos[u[i]]; if(u[i]>v[i])swap(u[i],v[i]); if(v[i]-u[i]==1||(v[i]==n&&u[i]==1))continue; u[++top]=u[i],v[top]=v[i]; } m=top; for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) if((u[i]<u[j]&&u[j]<v[i]&&v[i]<v[j])||(u[j]<u[i]&&u[i]<v[j]&&v[j]<v[i])) { insert(2*i-1,2*j); insert(2*i,2*j-1); insert(2*j-1,2*i); insert(2*j,2*i-1); } top=0; for(int i=1;i<=2*m;i++) if(!dfn[i])tarjan(i); if(jud())puts("YES"); else puts("NO"); } return 0; } |
计数器 9786903
OI 课件=>
OI 课件=>
为什么相交的情况不包含圆内两条边共点？
学长，传说[Hnoi2010]Planar可以用带权并查集做，可以教一下不？
不是带权的, 直接并查集就可以. 因为你可以看到这里加的其实都是无向边.