注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU303 计算几何+网络流+求出最小割  

2012-08-22 19:08:25|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
神题属性+一遍AC
虽说写了一个下午,但能在状态如此不佳的情况下把本题写过已经心满意足了
计算几何部分很简单,可以参见area那题。
网络流则直接套sap,也很简单
真正学会的是求最小割,在残量网络中由源点dfs,染色,然后连接染色与没染色的点之间的边即属于最小割
输出答案即可
然后为了命名方便,网络流部分使用了命名空间。
自觉代码写得蛮不错的

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<cmath>
using namespace std;

typedef double ld;
const int MAX=1000+10;
const int INF=1000000000;

struct point
{
int x,y;
void init(){scanf("%d %d",&x,&y);}
void print(){printf("%d %d ",x,y);}
point(int a,int b){x=a;y=b;}
point(){}
}a,b;

int dblcmp(int a)
{
if(a==0)return 0;
else if(a>0)return 1;
else return -1;
}

int chaji(const point& s,const point& a,const point& b)
{
return (a.x-s.x)*(b.y-s.y)-(a.y-s.y)*(b.x-s.x);
}

int cross(point& a,point& b,point& c,point& d)
{
return dblcmp(chaji(a,c,b))*dblcmp(chaji(a,b,d))>=0
&& dblcmp(chaji(c,d,a))*dblcmp(chaji(c,b,d))>=0;
}

int operator < (const point& a,const point& b)
{
return a.x!=b.x?(a.x<b.x):(a.y<b.y);
}

ld operator / (const point& a,const point& b)
{
return atan2(a.y-b.y,a.x-b.x);
}

map<point,int> lab;
int num,hash[MAX][MAX],cost[MAX][MAX],lable[MAX][MAX],tot;
point d[MAX];
vector< pair<ld ,int> > next[MAX];
vector<int> area[MAX];

int n;

void dfs(int first,int come,int u,int tot)
{
area[tot].push_back(u);
if(u==first)
return;
size_t i;
for(i=0;i<next[u].size();++i)
if(next[u][i].second==come)
break;
i=(i+1)%next[u].size();
int v=next[u][i].second;
hash[u][v]=tot;
dfs(first,u,v,tot);
}

void init()
{
int i,ss,tt;
point s,t;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
s.init();t.init();

if(!lab[s])
{
lab[s]=++num;
d[num]=s;
}
if(!lab[t])
{
lab[t]=++num;
d[num]=t;
}
ss=lab[s];tt=lab[t];

lable[ss][tt]=lable[tt][ss]=i;

scanf("%d ",&cost[ss][tt]);
cost[tt][ss]=cost[ss][tt];

hash[ss][tt]=hash[tt][ss]=0;

next[ss].push_back(make_pair(t/s,tt));
next[tt].push_back(make_pair(s/t,ss));
}
a.init();b.init();
}

int inPoly(point& a,int tot)
{
size_t i,j;
int ans=0;
point c(34633,22229);
for(i=0;i<area[tot].size();++i)
{
j=(i+1)%area[tot].size();
if(cross(a,c,d[ area[tot][i] ],d[ area[tot][j] ] ))
++ans;
}
return ans%2==1;
}

namespace M
{
struct Edge
{
int s,t,C,flow,next,id;
}e[MAX*MAX];
int begin[MAX],h[MAX],gap[MAX],tot,S,T,ans[MAX],color[MAX],ansflow;

void addedge(int s,int t,int c,int id)
{
e[tot].s=s;e[tot].t=t;e[tot].C=c;
e[tot].next=begin[s];begin[s]=tot;
e[tot].id=id;
tot++;

e[tot].s=t;e[tot].t=s;e[tot].C=0;
e[tot].next=begin[t];begin[t]=tot;
e[tot].id=id;
tot++;
}

int sap(int u,int flow)
{
if(u==T)
return flow;
int i,v,remain=flow,temp;
for(i=begin[u];i!=-1;i=e[i].next)
if(h[u]==h[v=e[i].t]+1 && e[i].C>e[i].flow)
{
temp=min(e[i].C-e[i].flow,remain);
temp=sap(v,temp);
e[i].flow+=temp;
e[i^1].flow-=temp;
remain-=temp;
if(!remain)
return flow-remain;
}
gap[h[u]]--;
if(!gap[h[u]])h[S]=tot+1;
++gap[++h[u]];
return flow-remain;
}

void paint(int u)
{
color[u]=1;
int i,v;
for(i=begin[u];i!=-1;i=e[i].next)
{
v=e[i].t;
if(e[i].C>e[i].flow && !color[v])
paint(v);
}
}

void maxflow()
{
memset(h,0,sizeof h);
memset(gap,0,sizeof gap);
while(h[S]<tot+1)
ansflow+=sap(S,INF);
paint(S);
for(int i=0;i<tot;++i)
if(color[e[i].s] && !color[e[i].t] && e[i].C)
ans[++ans[0]]=e[i].id;
}

void show()
{
printf("%d\n",ansflow);
int i;
printf("%d\n",ans[0]);
for(i=1;i<=ans[0];++i)
printf("%d ",ans[i]);
printf("\n");
}
}

void work()
{
int i,v,f1,f2,aa,bb,cc,id;
size_t j,k;
for(i=1;i<=num;++i)
sort(next[i].begin(),next[i].end());
for(i=1;i<=num;++i)
for(j=0;j<next[i].size();++j)
{
v=next[i][j].second;
if(!hash[i][v])
{
hash[i][v]=++tot;
dfs(i,i,v,tot);
}
}
for(i=1;i<=tot;++i)
{
f1=inPoly(a,i);f2=inPoly(b,i);
if( (f1 && f2) || (!f1 && !f2))
continue;
if(f1) M::S=i;
else M::T=i;
}
memset(M::begin,-1,sizeof M::begin);
for(i=1;i<=tot;++i)
for(j=0;j<area[i].size();++j)
{
k=(j+1)%area[i].size();
aa=hash[ area[i][j] ][ area[i][k] ];
bb=hash[ area[i][k] ][ area[i][j] ];
cc=cost[ area[i][k] ][ area[i][j] ];
id=lable[ area[i][k] ][ area[i][j] ];
M::addedge(aa,bb,cc,id);
}
M::maxflow();
M::show();
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
init();
work();
return 0;
}




  评论这张
 
阅读(367)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018