HDU 3931 Cross the Fire [陈题,无向图最小权点割]

Cross the Fire

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 146    Accepted Submission(s): 64


Problem Description
Our hero is planned to cross an important street, the other side of the street is the headquarters of the enemy. The whole street is a rectangle with length L and width W. Because the streets are sealed of the building block on both up and down side, we assumed people can only walk down on the street but not get out the up and down board.
In order to prevent our hero, the evil enemy layout N mines in the street. Due to internal staff informed in advance, the hero has known the distribution of all mines, and their explosion radius and explosion power. The mine enemy used is an amazing sense-mine, as long as the person come into its sensing radius, it will explode, due to unknown reasons, the explosion radius of each mine is same to its sensing radius. Heroes have a certain strength value at first, but once he touching a mine, he will lose some strength value same to the explosion power of this mine. Once the hero's strength value is not greater than zero, he will die.
Now hero want you to help him calculate whether there is a path so that he can live to reach the enemy headquarters. If he can live to cross the street, he wants to know the maximum remaining strength value after crossing the street. We assume the hero's path trajectory is arbitrary.
 

Input
The input consists of several test cases.
The first line contains four integers L, W, N and P– the length and the width of the street, the number of mines, and the initial strength value of hero, respectively(1 ≤ L ≤ 10000 ,1 ≤ W ≤ 10000, 1 ≤ N ≤ 250, 1 ≤ P ≤ 1000000). Each of the following N lines contains four integers Xi, Yi, Ri and Pi – the coordinates, the sensing radius(explosion radius) and the explosion power of i-th mine in the street (0 ≤ Xi ≤ L, 0 ≤ Yi ≤ W, 1 ≤ Ri ≤ 100, 1 ≤ Pi ≤ 10000). The coordinates and radius are given in meters, relative to the street: the southwestern corner of the street has coordinates (0, 0), and the northeastern corner of the street has coordinates (L, W).
Note that crossing the street may start at coordinate (0, ys ) for any 0 ≤ ys ≤ W and end at coordinate (L, ye ) for any 0 ≤ ye ≤ W . Neither ys nor ye need to be integer.
 

Output
For each input cases, if our hero cannot live to cross the street, please output “Our hero has been killed”; otherwise output the maximum remaining strength value after crossing the street.
 

Sample Input
130 340 5 2 10 50 100 1 130 130 100 1 70 170 100 1 0 180 100 1 60 260 100 1
 

Sample Output
1
 

Source

先自我吐槽:
一开始贪心建图来着。wa了。后来被肖神举出了反例。然后联想到了poj3281。果断最小割点权图必然要拆点的,而非一般建图或者贪心建图。因为错误建图会导致某点点权被重复使用,所以错误性显然。
给一组贪心建图反例,肖神给的。YM
s-1(10),s-2(10),1-3(5),2-3(5),3-4(5),3-5(5),4-t(10),5-t(10)
本组样例中3点的点权就被重复使用了,流出了错误割10,实际上应为5。
正确建图:
s-1(inf),s-2(inf),1-1'(10),2-2'(10),1-3(inf),2-3(inf),3-3'(5),3-4(inf),3-5(inf),4-4'(10),5-5'(10),4-t(inf),5-t(inf).

本题捉法:
YY半天圆交和路径规划,发现都不会写,于是场上悲剧了。赛后被人提醒最小割,果断有想法。唉,场上多yy才是王道。
建图:
本题中的炸弹如果想对“主角”造成困扰,至少要出现上连上边界,下连下边界,中间封住才可以。于是易得把边界做源汇,各圆做中继点的想法。
一开始的想法是边容量以两圆中较小的伤害值为准。
后来发现这种建图错误显然。
经各种神的提携之后,意识到无向图点权割果断要拆点转化为边割才可解,于是就有了如下建图:
每圆拆点,入点->出点,容量为点权。相交的圆以及和源汇相交的圆之间连边,容量正无穷。圆间无向,源汇和圆间无向。注意连边方式为出点->入点,分清出入点p,p'。
跑个最大流。这都是后话了。
弱爆了,要善于yy,多想想建图方式啊!!!

代码:
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
#include 
<cmath>
using namespace std;
#define maxn 505
#define maxm 260000
const int inf = ~0u >> 1;
struct circus
{
    
int x,y,r,p;
    circus(){}
    circus(
int a,int b,int c,int d):x(a),y(b),r(c),p(d){}
}cir[maxn];
struct edge
{
    
int p,next,val;
    edge(){}
    edge(
int a,int b,int c):p(a),next(b),val(c){}
}e[maxm];
int l,w,p,n,N,tot,flow[maxn],pre[maxn],v[maxn],arc[maxn],path[maxn],cnt[maxn],d[maxn];
void init()
{
    n 
= 2*+ 1;
    tot 
= 0;
    memset(v,
-1,sizeof(v));
    memset(cnt,
0,sizeof(cnt));
    memset(d,
0,sizeof(d));
    cnt[
0= n + 1;
}
void add(int p,int q,int val)
{
    e[tot] 
= edge(q,v[p],val);
    v[p] 
= tot++;
    e[tot] 
= edge(p,v[q],0);
    v[q] 
= tot++;
}
int mflow()
{
    
int s = 0,t = n;
    
int sum,now,k,loc,i,least;
    
bool flag;
    
for(int i = 0;i <= n;i++)arc[i] = v[i];
    
for(sum = 0,now = inf,i = s;d[s] < n + 1;)
    {
        flow[i] 
= now;
        
for(flag = false,k = arc[i];~k;k = e[k].next)
        {
            
if(e[k].val && d[i] == d[e[k].p] + 1)
            {
                now 
= min(now,e[k].val);
                pre[e[k].p] 
= i;
                path[e[k].p] 
= k;
                arc[i] 
= k;
                i 
= e[k].p;
                
if(i==t)
                {
                    
for(sum += now;i != s;i = pre[i])
                    {
                        e[path[i]].val 
-= now;
                        e[path[i]
^1].val += now;
                    }
                    now 
= inf;
                }
                flag 
= true;
                
break;
            }
        }
        
if(!flag)
        {
            
for(least = n + 1,k = v[i];~k;k = e[k].next)
            {
                
if(e[k].val && least > d[e[k].p])
                {
                    least 
= d[e[k].p];
                    loc 
= k;
                }
            }
            cnt[d[i]]
--;
            
if(!cnt[d[i]])
                
break;
            d[i] 
= least + 1;
            cnt[d[i]]
++;
            arc[i] 
= loc;
            
if(i != s)
            {
                i 
= pre[i];
                now 
= flow[i];
            }
        }
    }
    
return sum;
}
int main()
{
    
while(scanf("%d %d %d %d",&l,&w,&N,&p) == 4)
    {
        init();
        
for(int i = 1;i <= N;i++)
        {
            
int a,b,c,d;
            scanf(
"%d %d %d %d",&a,&b,&c,&d);
            cir[i] 
= circus(a,b,c,d);
        }
        
for(int i = 1;i <= N;i++)
        {
            add(i,i 
+ N,cir[i].p);
            
if(cir[i].y <= cir[i].r)
                add(
0,i,inf);
            
if(w - cir[i].y <= cir[i].r)
                add(i
+N,n,inf);
        }
        
for(int i = 1;i <= N;i++)
            
for(int j = i + 1;j <= N;j++)
            {
                
if((cir[i].x - cir[j].x) * (cir[i].x - cir[j].x) + (cir[i].y - cir[j].y) * (cir[i].y - cir[j].y) <= (cir[i].r + cir[j].r) * (cir[i].r + cir[j].r))
                {
                    add(i
+N,j,inf);
                    add(j
+N,i,inf);
                }
            }
        
int ans = mflow();
        
if(p > ans)
            printf(
"%d\n",p - ans);
        
else
            puts(
"Our hero has been killed");
    }
}

posted on 2011-08-13 00:57 BUPT-[aswmtjdsj] @ Penalty 阅读(485) 评论(0)  编辑 收藏 引用 所属分类: 图论网络流HDU Solution Report


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


<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜