锐客网

  1. 首页 > it技术 > >

图论（平面图的对偶图）

平面图我们离散课上讲过，在二维空间中可以写成不交叉边的图就是平面图，最小的非平面图有K5和K（3,3）
【图论（平面图的对偶图）】每个平面图都对应一个对偶图，对偶图中的最小环就是原图的最小割
如果删去对偶图中s-t这条边，就是相当于求最短路了
把原图中每个点在对偶图中标号，重新建图，在新图中跑最短路就行了
然后看一下平面图和对偶图之间的转化：
对偶图中的每一个点即为平面图中的某一个面，对偶图中任意两点间的线都是平面图中对应两平面公共边的割线，如果平面图中某一条边只属于一个面，那么在对偶图中就是一个环边
对偶图的边数等于平面图的边数，对偶图的点数等于平面图的面数

针对BZOJ1001

①把每一个图中的面积块当作新的点。 ②每一条边都与两个面相连，把面看作点后，这条边连接这两个面化作的点，权值不变。 ③连接起点与终点，把外面的最大平面分成两份，分别为最短路的起点与终点。 ④跑一边最短路即可。

我感觉难在建图上，别的都非常好说
建图必须好好研究一下
1 #include 2 #include 3 const int maxn=2000005; 4 int n,m,nm,cnt; 5 bool vi[maxn]; 6 int dis[maxn],g[maxn],q[maxn]; 7 struct Edge 8 { 9int t,next,w; 10 }e[4*maxn]; 11 void insert(int u,int v,int w) 12 { 13cnt++; e[cnt].t=v; e[cnt].w=w; e[cnt].next=g[u]; g[u]=cnt; 14cnt++; e[cnt].t=u; e[cnt].w=w; e[cnt].next=g[v]; g[v]=cnt; 15 } 16 void spfa() 17 { 18memset(dis,0x3f,sizeof(dis)); 19dis[0]=0; 20int h=0,t=1; 21q[t]=0; 22vi[0]=1; 23while(h!=t) 24{ 25h=h%maxn+1; 26int u=q[h]; 27vi[u]=0; 28for(int tmp=g[u]; tmp; tmp=e[tmp].next) 29{ 30int v=e[tmp].t; 31if(dis[v]>dis[u]+e[tmp].w) 32{ 33dis[v]=dis[u]+e[tmp].w; 34if(!vi[v]) 35{ 36t=t%maxn+1; 37vi[v]=1; 38q[t]=v; 39} 40} 41} 42} 43 } 44 int main() 45 { 46scanf("%d%d",&n,&m); 47nm=(n*m-m-n+1)<<1; 48int x; 49for(int j=1; j

转载于:https://www.cnblogs.com/aininot260/p/9623272.html

    推荐阅读


    上一篇：2017-0ctf-babyheap

    下一篇：运维|nginx error_page