题意：
给出一个平面图，每条边从不同方向各有一个跨越代价(或者不能跨越)；
求一个最小总跨越代价，使从某个平面区域能跨越到所有其他区域；
即在此平面图的对偶图上求最小树形图；
平面图中点数<=3000，区域数<=1000，跨越代价<=100；
题解：
实际上这是两道裸题。。。然后我作死的学了两种算法；
首先是平面图转对偶图：
首先将无向边拆成两条单向边，按顺/逆时针挂在端点上；
每一次从一条没有经过的单向边出发，深搜；
深搜每到达一个点，我们都找到从来的边顺/逆时针旋转，得到的第一个边继续深搜，搜到最开始的点时停止；
这个过程中因为每次都是找第一条边来搜，所以这个区域一定不包含其他区域的；
然后记录该区域编号，深搜回溯时将来时的每条边都记录这个编号；
搜索次数与平面区域数有关，每条边只会被搜索一次，而平面区域数与边数最多与顶点数同级；
所以如果使用二分查找，时间复杂度是O(nlogn)的吧。。。
(然而我这么懒当然写的是O(n^2)暴力)
转化成对偶图之后，就是应用最小树形图的朱刘算法了；
这个网上讲的似乎都很详细？
需要注意的地方就是找环的时候小心一些，不要将环外面的树也算进去；
当然了，这道题没有自环，不用做预处理；
时间复杂度是O(nm)；
代码：
#include<queue>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
namespace Graph
{
#define N 2100
#define M 50000
int X[M],Y[M],val[M],ce;
int next[M],to[M],head[N],cnt,tot;
int in[N],fa[N];
int n;
bool vis[N],inc[N];
void add(int x,int y,int v)
{
Y[++ce]=y;
X[ce]=x;
val[ce]=v;
}
void addedge(int x,int y)
{
to[++cnt]=y;
next[cnt]=head[x];
head[x]=cnt;
}
int dfs(int x)
{
inc[x]=1;
if(inc[fa[x]])
{
tot+=in[x];
return fa[x];
}
else
{
int temp=dfs(fa[x]);
if(temp&&x!=temp)
{
tot+=in[x];
return temp;
}
else if(x==temp)
{
tot+=in[x];
return 0;
}
}
inc[x]=0;
return 0;
}
int check()
{
for(int i=0;i<=n;i++)
if(!vis[i])
in[i]=0x3f3f3f3f,head[i]=0,inc[i]=1;
for(int i=1;i<=ce;i++)
{
if(!vis[X[i]]&&!vis[Y[i]])
{
if(in[Y[i]]>val[i])
{
in[Y[i]]=val[i];
fa[Y[i]]=X[i];
}
}
}
int ret=0;
for(int i=1;i<=n;i++)
if(!vis[i])
ret+=in[i];
cnt=0;
for(int i=1;i<=n;i++)
if(!vis[i])
addedge(fa[i],i);
static queue<int>q;
q.push(0);
while(!q.empty())
{
int x=q.front();
q.pop();
inc[x]=0;
for(int i=head[x];i;i=next[i])
{
q.push(to[i]);
}
}
for(int i=0;i<=n;i++)
if(!vis[i]&&inc[i])
{
memset(inc,0,sizeof(inc[0])*(n+1));
dfs(i);
return -1;
}
return ret;
}
int slove()
{
int ans,sum,i;
for(i=1,sum=0;i<=ce;i++)
{
sum+=val[i];
}
for(i=1;i<=n;i++)
add(0,i,sum+1);
tot=0;
while((ans=check())==-1)
{
for(i=1;i<=ce;i++)
{
if(inc[X[i]]&&!vis[Y[i]]&&!inc[Y[i]])
{
X[i]=n+1;
}
else if(!vis[X[i]]&&!inc[X[i]]&&inc[Y[i]])
{
val[i]-=in[Y[i]];
Y[i]=n+1;
}
}
for(i=0;i<=n;i++)
{
if(inc[i])
vis[i]=1,inc[i]=0;
}
n++;
}
return ans+tot-sum-1;
}
#undef N
#undef M
}
namespace Plane
{
#define N 3100
#define M 15000
struct Point
{
int x,y;
Point(){}
Point(int _,int __):x(_),y(__){}
}a[N];
struct Line
{
int x,y,num;
bool v;
double alpha;
friend bool operator <(Line a,Line b)
{
return a.alpha<b.alpha;
}
}l[M];
int next[M],to[M],num[M],head[N],ce;
bool v[M];
int val[M][2],X[M][2];
bool vis[N];
void add(int x,int y,int tnum,bool tv)
{
to[++ce]=y;
v[ce]=tv;
num[ce]=tnum;
next[ce]=head[x];
head[x]=ce;
}
int dfs(int x,int pre)
{
if(vis[x]) return ++Graph::n;
for(int i=head[x];i;i=next[i])
{
if(to[i]==pre)
{
i=next[i];
if(i)
return X[num[i]][v[i]]=dfs(to[i],x);
else
return X[num[head[x]]][v[head[x]]]=dfs(to[head[x]],x);
}
}
return 0;
}
void slove()
{
int n,m,i,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&x,&y,&val[i][0],&val[i][1]);
l[i+i-1].x=x,l[i+i-1].y=y,l[i+i-1].num=i,l[i+i-1].v=0;
l[i+i-1].alpha=atan2(a[y].y-a[x].y,a[y].x-a[x].x);
l[i+i].x=y,l[i+i].y=x,l[i+i].num=i,l[i+i].v=1;
l[i+i].alpha=atan2(a[x].y-a[y].y,a[x].x-a[y].x);
}
sort(l+1,l+m+m+1);
for(i=1;i<=m+m;i++)
{
add(l[i].x,l[i].y,l[i].num,l[i].v);
}
for(x=1;x<=n;x++)
{
vis[x]=1;
for(i=head[x];i;i=next[i])
{
if(!X[num[i]][v[i]])
X[num[i]][v[i]]=dfs(to[i],x);
}
vis[x]=0;
}
for(i=1;i<=m;i++)
{
if(val[i][0])
Graph::add(X[i][0],X[i][1],val[i][0]);
if(val[i][1])
Graph::add(X[i][1],X[i][0],val[i][1]);
}
}
#undef N
#undef M
}
int main()
{
Plane::slove();
printf("%d\n",Graph::slove());
return 0;
}
原文：http://blog.csdn.net/ww140142/article/details/49755573