锐客网

  1. 首页 > it技术 > >

BZOJ 2960(跨平面-平面图转对偶图求最小有向图)

对偶图


2960: 跨平面 Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 157 Solved: 65
[ Submit][ Status][ Discuss] Description BZOJ 2960(跨平面-平面图转对偶图求最小有向图)
文章图片

Input 　第一行两个整数n和m，表示点与线段的数目。
接下来n行，每行两个整数x和y，表示第i个点的坐标，点从1到n编号。
接下来m行，每行四个整数p,q,V1和V2，表示存在一条从第p个点连向第q个点的线段，激活p->q这个方向的费用为V1，另一个方向费用为V2。
保证若两条线段相交，则交点是它们的公共端点。

Output 输出一行一个正整数，表示最小总激活费用。

Sample Input 4 5
0 0
1 0
0 1
1 1
1 2 0 0
1 3 0 3
2 3 1 0
2 4 2 0
4 3 0 0
Sample Output 3 HINT
BZOJ 2960(跨平面-平面图转对偶图求最小有向图)
文章图片


对于100%的数据，n≤3000，区域数不超过1000，点坐标绝对值不超过1W，每条边激活费用不超过100。



Source 中国国家队清华集训 2012-2013 第二天 鸣谢lydrainbowcat



【BZOJ 2960(跨平面-平面图转对偶图求最小有向图)】求PLCG
在对偶图上建图，求最小有向生成树。



#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define For(i,n) for(int i=1; i<=n; i++) #define Fork(i,k,n) for(int i=k; i<=n; i++) #define Rep(i,n) for(int i=0; i=k; i--) #define RepD(i,n) for(int i=n; i>=0; i--) #define Forp(x) for(int p=pre[x]; p; p=next[p]) #define Forpiter(x) for(int &p=iter[x]; p; p=next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define pb push_back #define mp make_pair #define MAXN (4000+50) #define eps (1e-3) #define MAXE (3000*3000+10) typedef long long ll; namespace geometry { struct P { int x,y; P(double x=0,double y=0):x(x),y(y){} friend istream& operator >> (istream &_,P &p) { scanf("%d%d",&p.x,&p.y); return _; } }; typedef P V; V operator + (V A,V B) {return V(A.x+B.x,A.y+B.y); } V operator - (V A,V B) {return V(A.x-B.x,A.y-B.y); } double Arctan2(const P p){return atan2(p.y,p.x); } }; using namespace geometry; P points[MAXN]; struct node{ // define a edge which has a vector and a startpoint node *another; double alpha; int to,cost,belong; node(){} node(double _alpha,int _to,int _cost):another(NULL),alpha(_alpha),to(_to),cost(_cost){belong=0; } void print(){ cout< a[MAXN]; vector::iterator it; bool Compare(const node *a, const node *b) { return a->alpha < b->alpha; } void Add(int x,int y,int t1,int t2) { if (!t1) t1=INF; if (!t2) t2=INF; V v=points[y] - points[x]; node *node1=new node(Arctan2(v),y,t1); node *node2=new node(Arctan2(P(0,0)-v),x,t2); node1->another = node2; node2->another = node1; a[x].pb(node1); a[y].pb(node2); }void DFS(int x, node * from, int aim,int cnt){ 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 , cnt ); }struct edge{ int u,v,w; edge(){} edge(int _u,int _v,int _w):u(_u),v(_v),w(_w){} }e[MAXE]; int tot=0; int id[MAXN],in[MAXN],pre[MAXN],vis[MAXN]; int MST_Directed(int root,int numv,int nume) { int ans=0; while (1) { For(i,numv) in[i]=INF,pre[i]=INF; For(i,nume) { int u=e[i].u,v=e[i].v,w=e[i].w; if (w>n>>m; For(i,n) scanf("%d%d",&points[i].x,&points[i].y); For(i,m) { int x,y,t1,t2; scanf("%d%d%d%d",&x,&y,&t1,&t2); Add(x,y,t1,t2); } For(i,n) sort(a[i].begin(),a[i].end(),Compare); int cnt=0; For(x,n) { for( it = a[x].begin() ; it!=a[x].end() ; it++ ) { if (!(**it).belong) { DFS((**it).to,*it,x,++cnt); } } } For(x,n) { vector::iterator it; for( it = a[x].begin() ; it!=a[x].end() ; it++ ) { if (INF!=(**it).cost) { e[++tot]=edge((*it)->another->belong,(*it)->belong,(**it).cost); } } } int ans=0; For(i,cnt) { e[++tot]=edge(cnt+1,i,0x1010101); } cout<








    推荐阅读


    上一篇：从零开始手撸WebGL3D引擎1: 搭建项目框架

    下一篇：逆向|虚拟内存的实现方法和过程