The Fourth Dimension Space

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

#

POJ 2391 Ombrophobic Bovines 网络流

这提相当经典啊,这题相当猥琐啊。。。。
无向图中给出N个点,M条边,每个点有当前囤积流量和最大容量,任意两个点之间有距离,首先保证所有的流量都可以被节点吸收(即不超过最大容量),然后将流量跑的最大距离限制到最小。
做法:SAP+二分+Floyd
1.首先预处理出任意两点之间的最短路,二分最大距离mid;
2.将每个节点拆成i*2 i*2+1,i*2+1代表流出的点out[i],i*2代表流进的点in[i],前者向后者连一条INF的边。
3.建立超级源s,向每个点in[i],连一条当前囤积流量的边,每个点out[i]向超级汇t连一条最大容量的边。
4.在floyd之后的数组中枚举每两个点之间的最短距离,如果<=mid就建立一条out[i]->in[j]的边
跑最大流,如果满流,下降上界,否则提高下界。

这题做了收获很大,学会了控制初始流量的方法和最后流量全部控制在容量内的方法。
另外就是拆点,分成两个点之后,限制了只要进来的流量就一定囤积在该点,由于这个点本身有初始流量,两个点之间连的那条边可以保证自己的流量也可以不流走。非常精彩的构图^_^
PS:顺便说一下的是:虽然这个图是无向图,但是根据题意,走任意方向互不干扰,所以可以拆成两条有向边。一旦有流量经过这条边,那么流量不会流走,也就说明这个流量必须也只能走这么长的距离,这个锁定技巧很不错,于是就能二分了。。。


int n,m;
int s,t;
int now[maxn];
int cap[maxn];

bint mat[maxn][maxn];


bint tol
=0;
void input()
{
    tol
=0;
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
        {
            
if(i==j)mat[i][j]=0;
            
else mat[i][j]=INF;
        }

    
for(int i=0;i<n;i++)
    {
        scanf(
"%d%d",&now[i],&cap[i]);
        tol
+=now[i];
    }
    
for(int i=0;i<m;i++)
    {
        
int u,v;
        bint w;
        scanf(
"%d%d%lld",&u,&v,&w);
        u
--;
        v
--;
        
if(w<mat[u][v])
            mat[u][v]
=mat[v][u]=w;
    }

}


void floyd()
{
    
for(int k=0;k<n;k++)
        
for(int i=0;i<n;i++)
            
for(int j=0;j<n;j++)
            {
                
if(mat[i][k]!=INF&&mat[k][j]!=INF)
                    
if(mat[i][k]+mat[k][j]<mat[i][j])
                        mat[i][j]
=mat[i][k]+mat[k][j];
            }
}


//in node : i*2;
//out node: i*2+1
//node sum: [0,2*n-1]
//s: 2*n
//t: 2*n+1
//tol:2*n+2

bool check(bint mid)
{
    
for(int i=0;i<2*n+2;i++)
        adj[i]
=NULL;
    len
=0;
    
for(int i=0;i<n;i++)
        
for(int j=0;j<n;j++)
        {
            
if(i==j)continue;
            
if(mat[i][j]!=INF&&mat[i][j]<=mid)
            {
                insert(i
*2+1,j*2,INF);
            }
        }
    
for(int i=0;i<n;i++)
    {
        insert(s,i
*2+1,now[i]);
        insert(i
*2+1,i*2,INF);
    }
    
for(int i=0;i<n;i++)
        insert(i
*2,t,cap[i]);
    
if(sap(t+1,s,t)==tol)
        
return true;
    
else
        
return false;
}

int main()
{

    
while(scanf("%d%d",&n,&m)!=EOF)
    {
        input();
        floyd();
        s
=2*n;
        t
=2*n+1;
        bint l
=0;
        bint r
=INF;
        bint ans
=-1;
        
while(l<=r)
        {
            bint mid
=(l+r)>>1;
            
if(check(mid)==true)
            {
                r
=mid-1;
                ans
=mid;
            }
            
else
                l
=mid+1;
        }
        printf(
"%lld\n",ans);
    }
    
return 0;
}


posted @ 2010-11-11 20:01 abilitytao 阅读(2016) | 评论 (1)编辑 收藏

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 @ 2010-11-09 20:27 abilitytao 阅读(267) | 评论 (0)编辑 收藏

杭州现场赛 B题 状态压缩DP

     摘要: 其实思路很简单,只是敲代码的时候很容易敲错,MD,居然为了一个Pn>=n写成了Pn>n NC地检查了一个上午。如果是现场就悲剧了。。。 #include<iostream>#include<queue>#include<algorithm>using namespace std;#define INF 100...  阅读全文

posted @ 2010-11-09 15:35 abilitytao 阅读(307) | 评论 (0)编辑 收藏

PKU 3301 Texas Trip

枚举矩形的旋转角度,再将所有点转回来,然后用面积最小的与轴平行的正方形覆盖。
可以建立映射关系area=f(θ),f(θ)感觉上是凹函数,故三分。
#include<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;
double const Pi=acos(-1.0);

#define eps 1e-8
int const maxn=31;
int n;
struct point 
{
    
double x,y;
}
p[maxn];

point rotate(point p,
double theta)//逆时针旋转theta度
{
    point ans;
    ans.x
=p.x*cos(theta)+p.y*sin(theta);
    ans.y
=-p.x*sin(theta)+p.y*cos(theta);
    
return ans;
}


double cal(double theta)
{
    point pp[maxn];
    
for(int i=0;i<n;i++)
        pp[i]
=rotate(p[i],-theta);
    
double minx=1000000000.0;
    
double maxx=-1000000000.0;
    
double miny=1000000000.0;
    
double maxy=-1000000000.0;
    
for(int i=0;i<n;i++)
    
{
        
if(pp[i].x<minx)
            minx
=pp[i].x;
        
if(pp[i].x>maxx)
            maxx
=pp[i].x;
        
if(pp[i].y<miny)
            miny
=pp[i].y;
        
if(pp[i].y>maxy)
            maxy
=pp[i].y;
    }

    
if((maxx-minx)>(maxy-miny))
        
return (maxx-minx)*(maxx-minx);
    
else
        
return (maxy-miny)*(maxy-miny);
}



int main()
{
    
int ca;
    scanf(
"%d",&ca);
    
while(ca--)
    
{

        scanf(
"%d",&n);
        
for(int i=0;i<n;i++)
            scanf(
"%lf%lf",&p[i].x,&p[i].y);
        
double l=0;
        
double r=Pi;
        
while(l+eps<=r)
        
{
            
double mid=(l+r)/2;
            
double mmid=(mid+r)/2;
            
if(cal(mid)<cal(mmid))
                r
=mmid;
            
else
                l
=mid;
        }

        printf(
"%.2lf\n",cal(l));

    }


    
return 0;
}

posted @ 2010-11-08 02:19 abilitytao 阅读(258) | 评论 (0)编辑 收藏

HDOJ 3400 三分法

1Y。只是不明白为什么可以套两个三分,不过从实际情况来看,在第一条直线上三分应该也是符合凸函数性质的。

#include<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;

#define eps 1e-8


struct point
{
    
double x,y;
}
;
point a,b,c,d;
double p,q,r;

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


double cal(double t1,double t2)//以t1,t2为参数算出时间
{
    point tm1;
    point tm2;
    tm1.x
=a.x+(b.x-a.x)*t1;
    tm1.y
=a.y+(b.y-a.y)*t1;

    tm2.x
=c.x+(d.x-c.x)*t2;
    tm2.y
=c.y+(d.y-c.y)*t2;


    
return dist(tm1,a)/p+dist(tm2,d)/q+dist(tm1,tm2)/r;
}



double sanfen(double t1)//在确定t1的基础上得最小值
{
    
double l=0;
    
double r=1;
    
while(l+eps<=r)
    
{

        
double mid=(l+r)/2;
        
double mmid=(mid+r)/2;
        
if(cal(t1,mid)<cal(t1,mmid))
            r
=mmid;
        
else
            l
=mid;
    }

    
return cal(t1,l);
}




int main()
{
    
int ca;
    scanf(
"%d",&ca);
    
while(ca--)
    
{
        scanf(
"%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
        scanf(
"%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
        
//
        scanf("%lf%lf%lf",&p,&q,&r);

        
double l,r;
        l
=0;r=1;
        
while(l+eps<=r)
        
{

            
double mid=(l+r)/2;
            
double mmid=(mid+r)/2;
            
if(sanfen(mid)<sanfen(mmid))
                r
=mmid;
            
else
                l
=mid;
        }

        printf(
"%.2lf\n",sanfen(l));
    }


    
return 0;
}

posted @ 2010-11-07 20:57 abilitytao 阅读(263) | 评论 (0)编辑 收藏

ZOJ 3203 Light Bulb (三分法)

这么简单的东西今天才接触到,原来单调的时候用二分,凸的时候用三分(当然求导也行,只是一般解不出来),三分可代替二分。

公式:x属于区间[D(H-h)/H,D]
影子长度=return (D*h-D*H+x*H)/x +(D-x);

#include<iostream>
#include
<cstdio>
#include
<cmath>
using namespace std;

#define eps 1e-9
double D,H,h;


double cal(double x)
{
    
return (D*h-D*H+x*H)/+(D-x);
}


int main()
{
    
int ca;
    scanf(
"%d",&ca);

    
while(ca--)
    
{

        scanf(
"%lf%lf%lf",&H,&h,&D);
        
double l,r;
        l
=D*(H-h)/H;r=D;
        
while(fabs(r-l)>=eps)
        
{
            
double mid=(l+r)/2;
            
double mmid=(r+mid)/2;
            
if(cal(mid)>cal(mmid))
                r
=mmid;
            
else
                l
=mid;
        }


        printf(
"%.3lf\n",cal(l));
    }


    
return 0;
}

posted @ 2010-11-07 18:28 abilitytao 阅读(491) | 评论 (1)编辑 收藏

三分法——求解凸性函数的极值问题(转)

二分法作为分治中最常见的方法,适用于单调函数,逼近求解某点的值。但当函数是凸性函数时,二分法就无法适用,这时三分法就可以“大显身手”~~


       如图,类似二分的定义Left和Right,mid = (Left + Right) / 2,midmid = (mid + Right) / 2; 如果mid靠近极值点,则Right = midmid;否则(即midmid靠近极值点),则Left = mid;

程序模版如下:

double Calc(Type a)
{
    /* 根据题目的意思计算 */
}

void Solve(void)
{
    double Left, Right;
    double mid, midmid;
    double mid_value, midmid_value;
    Left = MIN; Right = MAX;
    while (Left + EPS < Right)
    {
        mid = (Left + Right) / 2;
        midmid = (mid + Right) / 2;
        mid_area = Calc(mid);
        midmid_area = Calc(midmid);
        // 假设求解最大极值.
        if (mid_area >= midmid_area) Right = midmid;
        else Left = mid;
    }
}

现根据几道的OJ题目来分析三分法的具体实现。

buaa 1033 Easy Problem
http://acm.buaa.edu.cn/oj/problem_show.php?c=0&p=1033

题意为在一条线段上找到一点,与给定的P点距离最小。很明显的凸性函数,用三分法来解决。
Calc函数即为求某点到P点的距离。

ZOJ 3203 Light Bulb
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203


如图,人左右走动,求影子L的最长长度。
根据图,很容易发现当灯,人的头部和墙角成一条直线时(假设此时人站在A点),此时的长度是影子全在地上的最长长度。当人再向右走时,影子开始投影到墙上,当人贴着墙,影子长度即为人的高度。所以当人从A点走到墙,函数是先递增再递减,为凸性函数,所以我们可以用三分法来求解。

下面只给出Calc函数,其他直接套模版即可。
double Calc(double x)
{
    return (h * D - H * x) / (D - x) + x;
}

heru 5081 Turn the corner 08年哈尔滨regional网络赛
http://acm.hrbeu.edu.cn/index.php?act=problem&id=1280


汽车拐弯问题,给定X, Y, l, d判断是否能够拐弯。首先当X或者Y小于d,那么一定不能。
其次我们发现随着角度θ的增大,最大高度h先增长后减小,即为凸性函数,可以用三分法来求解。

这里的Calc函数需要比较繁琐的推倒公式:
s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
其中s为汽车最右边的点离拐角的水平距离, h为里拐点最高的距离, θ范围从0到90。

POJ 3301 Texas Trip
http://acm.pku.edu.cn/JudgeOnline/problem?id=3301

题意为给定n(n <= 30)个点,求出饱含这些点的面积最小的正方形。

有两种解法,一种为逼近法,就是每次m分角度,求出最符合的角度,再继续m分,如此进行times次,即可求出较为精确的解。(m 大概取10, times取30即可)

第二种解法即为三分法,首先旋转的角度只要在0到180度即可,超过180度跟前面的相同的。坐标轴旋转后,坐标变换为:
X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;

至于这题的函数是否是凸性的,为什么是凸性的,我也无法给出准确的证明,希望哪位路过的大牛指点一下~~

例题更新(2010.5.5)
hdu 3400 Line belt

http://acm.hdu.edu.cn/showproblem.php?pid=3400
典型的三分法,先三分第一条线段,找到一个点,然后根据这个点再三分第二条线段即可,想出三分的思路基本就可以过了。

对于求解一些实际问题,当公式难以推导出来时,二分、三分法可以较为精确地求解出一些临界值,且效率也是令人满意的。

/* czyuan原创,转载请注明出处。*/

转自:http://hi.baidu.com/czyuan_acm/blog/item/8cc45b1f30cefefde1fe0b7e.html

posted @ 2010-11-07 16:00 abilitytao 阅读(1295) | 评论 (0)编辑 收藏

POJ 3189 Steady Cow Assignment 网络流

题意: 表示题意看不懂,不够最后自己YY出来了。
简化一下题意可以如下描述:
给一个N*B的矩阵,N是牛的数量,B是牛舍的数量,每头牛对应一个牛舍序列(偏好是骗人的,不用管),每个牛舍有个容量C[i].
再给两个指针l,r.指向矩阵的两列(l<=r),现在规定l,r确定后,这些牛只能住进[l,r]中间区域的牛舍,问是否可以安排?如果可以,问r-l+1最小值是多少。


做法:网络流。这个枚举的思想很巧妙,反正我自己是想不到。。。
如果某个[l,r]区间可以安排的话那么[l,r+1] to [l,b]肯定可以安排。所以应该l++;
否则r++;

这题值得再研究下.


int n,b;
//牛[0,n-1]
//棚[n,n+b-1]
//超级源[n+b]
//超级汇[n+b+1]
//共n+b+2个结点
int a[maxn][25];
int c[25];


bool check(int l,int r)
{
    
for(int i=0;i<n+b+2;i++)
        adj[i]
=NULL;
    len
=0;
    
int s=0;
    
int t=n+b+1;
    
for(int i=1;i<=n;i++)
    
{
        
for(int j=l;j<=r;j++)
        
{

            insert(i,n
+a[i][j],1);
        }

    }

    
for(int i=1;i<=n;i++)
        insert(s,i,
1);
    
for(int i=1;i<=b;i++)
    
{

        insert(n
+i,t,c[i]);
    }

    
if(dinic(n+b+2,s,t)==n)
        
return true;
    
else
        
return false;
}


int main()
{
        
while(scanf("%d%d",&n,&b)!=EOF)
        
{

    

    
            
for(int i=1;i<=n;i++)
                
for(int j=1;j<=b;j++)
                    scanf(
"%d",&a[i][j]);
            
//
            for(int i=1;i<=b;i++)
                scanf(
"%d",&c[i]);
            
int l=1;
            
int r=1;
            
int ans=b;
            
while(l<=r&&r<=b)
            
{
                
if(ans==1)
                    
break;
                
if(r-l+1>=ans)
                
{
                    l
++;
                    
continue;
                }

                
if(check(l,r))
                
{
            
                    
if((r-l+1)<ans)
                        ans
=(r-l+1);
                    l
++;
                }

                
else
                    r
++;
            }

            printf(
"%d\n",ans);
        }


    
return 0;
}

posted @ 2010-11-07 02:06 abilitytao 阅读(1186) | 评论 (0)编辑 收藏

POJ 2455 Secret Milking Machine(二分+网络流)

题意:n个点的一个无向图,在保证存在t条从1到n的不重复路径(任意一条边都不能重复)的前提下,要使得这t条路径上的最大的那条边最小。
解法:二分t条路径上的最大边权,对原图的每一条边如果其<=mid,添加一条容量是1的边(正反都加上),然后跑一遍最大流,如果流量>=t,说明可以安排。迭代得最小值即可。

PS:我一直以为无向图不能拆成2条相反边的,但是这个题用这个做法却AC了。由于被那道two shortest题目影响,我觉得是不是也要先求出最短路径树然后把dis[i]+w[i][j]>=dis[j]的边建起来,把无向边转化成有向边来做,但是这样却wa了,不知道为什么。也许这个题恰好能拆边吧。
PSS:这题卡sap,用dinic才过掉

int mat[maxn][maxn];
int n,m,t;

struct node2{
    
int a,b,c;
}
ee[40010];

void input()
{

    
//scanf("%d%d%d",&n,&m,&t);
    /*
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {

            if(i==j)mat[i][j]=0;
            else mat[i][j]=INF;
        }
        
*/

    
for(int i=0;i<m;i++)
    
{
        
int a,b,c;
        scanf(
"%d%d%d",&a,&b,&c);
        a
--;b--;
        ee[i].a
=a;ee[i].b=b;ee[i].c=c;
    
/*    if(c<mat[a][b])
            mat[a][b]=mat[b][a]=c;
            
*/

    }

}


/*
int dis[maxn];
int use[maxn];
void SPFA(int n,int s)
{

    fill(dis,dis+n,INF);
    fill(use,use+n,0);
    dis[s]=0;
    use[s]=1;
    queue<int>Q;
    Q.push(s);
    while(!Q.empty())
    {

        int x=Q.front();Q.pop();
        use[x]=0;
        for(int i=0;i<n;i++)
        {

            if(dis[x]+mat[x][i]<dis[i])
            {
                dis[i]=dis[x]+mat[x][i];
                if(!use[i])
                {
                    use[i]=1;
                    Q.push(i);
                }
            }
        }
    }
}
*/


bool check(int mid)
{

    
for(int i=0;i<n;i++)
        adj[i]
=NULL;
    len
=0;
    
for(int i=0;i<m;i++)
    
{
        
int a=ee[i].a;
        
int b=ee[i].b;
        
/*
        if(dis[a]+ee[i].c>=dis[b]&&ee[i].c<=mid)
            insert(a,b,1);
        else if(dis[b]+ee[i].c>=dis[a]&&ee[i].c<=mid)
            insert(b,a,1);
            
*/

        
if(ee[i].c<=mid)
        
{
            insert(a,b,
1);
            insert(b,a,
1);
        }

    }

    
return dinic(n,0,n-1)>=t;
}


int main()
{
    scanf(
"%d%d%d",&n,&m,&t);
    
        input();
        
//SPFA(n,0);
        int l=0;
        
int r=1000000;
        
int ans=-1;
        
while(l<=r)
        
{
            
int mid=(l+r)>>1;
            
if(check(mid))
            
{
                ans
=mid;
                r
=mid-1;
            }

            
else
                l
=mid+1;
        }

        printf(
"%d\n",ans);

    

    
return 0;


}

posted @ 2010-11-06 23:20 abilitytao 阅读(1290) | 评论 (0)编辑 收藏

POJ 2112 Optimal Milking 网络流+二分

越来越感觉网络流+二分还挺常见的啊,而且往往是要求一个最大的量最小的时候用。
题意:有K台机器,C头奶牛,他们之间的距离用一个邻接矩阵表示,每台机器能容纳M头奶牛喝奶。现在给这C头奶牛分配机器,满足两个要求:
1.这C头奶牛可以找到机器(这个条件由M限制)
2.C头奶牛中走的路程最长的奶牛 要让他的路程尽量短。
问这个最长距离的最小值(有点绕。。。)

做法:首先floyd一下,与处理处点对之间的最短路长度。
二分距离,保存原图中<=mid的边,添加超级源汇,s到每头牛建立容量是1的边,每台机器到t建立容量是M的边,跑一遍最大流,如果满流,说明C头牛都可以在mid的限制条件下被分配。取距离最小值即可.

模板就不贴了,构图如下:

int mat[maxn][maxn];
int K,C,M;
int n;//记录牛和机器的总数量
void input()
{
    scanf(
"%d%d%d",&K,&C,&M);
    n
=K+C;
    
for(int i=0;i<n;i++)
    
{

        
for(int j=0;j<n;j++)
        
{
            scanf(
"%d",&mat[i][j]);
            
if(mat[i][j]==0&&(i!=j))
                mat[i][j]
=INF;//表示不连通
        }

    }

}


void floyd()
{
    
for(int k=0;k<n;k++){
        
for(int i=0;i<n;i++){
            
for(int j=0;j<n;j++)
            
{
                
if(mat[i][k]!=INF&&mat[k][j]!=INF)
                
{
                    
if(mat[i][k]+mat[k][j]<mat[i][j])
                        mat[i][j]
=mat[i][k]+mat[k][j];
                }

            }

        }

    }

}



bool check(int mid)
{
    
int s=n;
    
int t=n+1;//公有n+2个结点
    
//
    for(int i=0;i<=t;i++)
        adj[i]
=NULL;
    len
=0;//重新构图

    
for(int i=K;i<n;i++)
    
{
        
for(int j=0;j<K;j++)
        
{
            
if(mat[i][j]<=mid)
            
{

                insert(i,j,
1);
            }

        }

    }

    
for(int i=K;i<n;i++)
        insert(s,i,
1);
    
for(int i=0;i<K;i++)
        insert(i,t,M);
    
return sap(t+1,s,t)==C;
}




int main()
{

    input();
    floyd();
    
int l=0;
    
int r=INF;
    
int ans=-1;
    
while(l<=r)
    
{
        
int mid=(l+r)>>1;
        
if(check(mid))
        
{
            r
=mid-1;
            ans
=mid;
        }

        
else
            l
=mid+1;
    }

    printf(
"%d\n",ans);



    
return 0;
}


PS:开始没搞清楚题目干嘛给邻接矩阵,那么多输入都是没用的东西。
不过倒是自然地帮你编了号。。。额。。。只要加个s,t,省事了。。。

posted @ 2010-11-06 15:49 abilitytao 阅读(1505) | 评论 (0)编辑 收藏

仅列出标题
共42页: First 4 5 6 7 8 9 10 11 12 Last