The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3498 March of the Penguins 网络流

题意:给出一个有源网络流图,每个点射出的流量有上界限制(除源点外),问是否可以在图中找到汇点使得该网络流图满流。
做法:感觉这题唯一的收获就是学会了控制结点射出流量的方法,拆点,i->i`点连一条容量为限制数的边,这样就可以控制这个点流出的流量了。


struct node2
{
    
double x,y;
    
int a,b;
}
p[maxn];
int n;
double D;


double dist(node2 a,node2 b)
{
    
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}


void input()
{
    scanf(
"%d %lf",&n,&D);
    
for(int i=0;i<n;i++)
        scanf(
"%lf%lf%d%d",&p[i].x,&p[i].y,&p[i].a,&p[i].b);
}

int s;
int tol;

//入结点为2*i
//出结点为2*i+1 ^_^
void get()
{
    
for(int i=0;i<2*n+1;i++)
        adj[i]
=NULL;
    len
=0;
    tol
=0;

    
for(int i=0;i<n;i++)
        insert(i
*2,i*2+1,p[i].b);
    
for(int i=0;i<n;i++)
    
{
        insert(s,i
*2,p[i].a);
        tol
+=p[i].a;
    }

    
for(int i=0;i<n;i++)
    
{
        
for(int j=0;j<n;j++)
        
{
            
if(i==j)continue;
            
if(dist(p[i],p[j])<=D)
                insert(i
*2+1,j*2,INF);
        }

    }

}


int ans[1000];
int pans;

int main()
{
    
int ca;
    scanf(
"%d",&ca);
    
while(ca--)
    
{
        input();
        
        pans
=0;
        s
=n*2;
        
for(int i=0;i<n;i++)
        
{
            
get();
            
if(sap(s+1,s,i*2)==tol)
                ans[pans
++]=i;
        }

        
if(pans==0)
            printf(
"-1\n");
        
else
        
{

            
for(int i=0;i<pans-1;i++)
                printf(
"%d ",ans[i]);
            printf(
"%d\n",ans[pans-1]);
        }

    
    }

    
return 0;


}

posted on 2010-11-09 20:27 abilitytao 阅读(291) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理