题目大意：给定一张平面图，求对偶图的最小树形图
【朱刘算法|BZOJ 2960 跨平面 对偶图+朱刘算法】这题TM考了我两遍！！两遍！！我拿了两遍MST的60分！
世界你赢了 你逼着我学了朱刘算法233

#include #include #include #include #include #include #define M 3030 #define INF 0x3f3f3f3f using namespace std; struct Point{ int x,y; Point() {} Point(int _,int __):x(_),y(__) {} friend istream& operator >> (istream &_,Point &p) { scanf("%d%d",&p.x,&p.y); return _; } friend Point operator - (const Point &p1,const Point &p2) { return Point(p1.x-p2.x,p1.y-p2.y); } friend double Arctan2(const Point &p) { return atan2(p.y,p.x); } }points[M]; struct List{ List *another; int to,len,belong; double alpha; List() {} List(int _,int __,double ___): another(0x0),to(_),len(__),belong(0),alpha(___) {} }; int n,m,cnt=1; vector a[M]; bool Compare(const List *x,const List *y) { return x->alpha < y->alpha ; } void Add(int x,int y,int t1,int t2) { if(!t1) t1=INF; if(!t2) t2=INF; Point p=points[y]-points[x]; List *temp1=new List(y,t1,Arctan2(p)); List *temp2=new List(x,t2,Arctan2(Point(0,0)-p)); temp1->another=temp2; temp2->another=temp1; a[x].push_back(temp1); a[y].push_back(temp2); } void DFS(int x,List *from,int aim) { from->belong=cnt; if(x==aim) return ; vector::iterator it=lower_bound(a[x].begin(),a[x].end(),from->another,Compare); it++; if(it==a[x].end()) it=a[x].begin(); DFS((*it)->to,*it,aim); } namespace Dual_Graph{ struct edge{ int x,y,z; edge() {} edge(int _,int __,int ___): x(_),y(__),z(___) {} }edges[100100]; int n,m; void Add(int x,int y,int z) { ++m; edges[m].x=x; edges[m].y=y; edges[m].z=z; } int DMST() { static int f[M],from[M],v[M],T; static bool deleted[M]; int i,j,re=0; while(1) { memset(f,0x3f,sizeof f); memset(from,0,sizeof from); for(i=1; i<=m; i++) if(f[edges[i].y]>edges[i].z) { f[edges[i].y]=edges[i].z; from[edges[i].y]=edges[i].x; } for(i=2; i<=n; i++) if(!deleted[i]) if(f[i]==INF) return -1; memset(v,0,sizeof v); for(i=2; i<=n; i++) if(!deleted[i]) { for(++T,j=i; j!=1&&!v[j]; j=from[j]) v[j]=T; if(v[j]==T) break; } if(i==n+1) { for(i=2; i<=n; i++) if(!deleted[i]) re+=f[i]; return re; } memset(v,0,sizeof v); i=j; do{ i=from[i]; re+=f[i]; v[i]=true; deleted[i]=true; }while(i!=j); deleted[j]=false; int cnt=0; for(i=1; i<=m; i++) { if(!v[edges[i].x]&&!v[edges[i].y]) edges[++cnt]=edges[i]; else if(v[edges[i].x]&&v[edges[i].y]) continue; else if(v[edges[i].x]) edges[++cnt]=edge(j,edges[i].y,edges[i].z); else edges[++cnt]=edge(edges[i].x,j,edges[i].z-f[edges[i].y]); } m=cnt; } } } int main() { //freopen("square.in","r",stdin); //freopen("square.out","w",stdout); int i,x,y,t1,t2; cin>>n>>m; for(i=1; i<=n; i++) cin>>points[i]; for(i=1; i<=m; i++) { scanf("%d%d%d%d",&x,&y,&t1,&t2); Add(x,y,t1,t2); } for(i=1; i<=n; i++) sort(a[i].begin(),a[i].end(),Compare); for(x=1; x<=n; x++) { vector::iterator it; for(it=a[x].begin(); it!=a[x].end(); it++) if(!(*it)->belong) ++cnt,DFS((*it)->to,*it,x); } for(x=1; x<=n; x++) { vector::iterator it; for(it=a[x].begin(); it!=a[x].end(); it++) if((*it)->len!=INF) Dual_Graph::Add((*it)->another->belong,(*it)->belong,(*it)->len); } Dual_Graph::n=cnt; for(i=2; i<=cnt; i++) Dual_Graph::Add(1,i,0x1010101); cout<