#
这提相当经典啊，这题相当猥琐啊。。。。
无向图中给出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;
}
题意：给出一个有源网络流图，每个点射出的流量有上界限制（除源点外），问是否可以在图中找到汇点使得该网络流图满流。
做法：感觉这题唯一的收获就是学会了控制结点射出流量的方法，拆点，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;
}
摘要: 其实思路很简单，只是敲代码的时候很容易敲错，MD，居然为了一个Pn>=n写成了Pn>n NC地检查了一个上午。如果是现场就悲剧了。。。
#include<iostream>#include<queue>#include<algorithm>using namespace std;#define INF 100...
阅读全文
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;
}
二分法作为分治中最常见的方法，适用于单调函数，逼近求解某点的值。但当函数是凸性函数时，二分法就无法适用，这时三分法就可以“大显身手”～～
如图，类似二分的定义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
题意为在一条线段上找到一点，与给定的Ｐ点距离最小。很明显的凸性函数，用三分法来解决。
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，那么一定不能。
其次我们发现随着角度θ的增大，最大高度ｈ先增长后减小，即为凸性函数，可以用三分法来求解。
这里的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
题意： 表示题意看不懂，不够最后自己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;
}
题意：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;
}
越来越感觉网络流+二分还挺常见的啊，而且往往是要求一个最大的量最小的时候用。
题意：有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，省事了。。。