#
這提相當(dāng)經(jīng)典啊，這題相當(dāng)猥瑣啊。。。。
無向圖中給出N個(gè)點(diǎn)，M條邊，每個(gè)點(diǎn)有當(dāng)前囤積流量和最大容量，任意兩個(gè)點(diǎn)之間有距離，首先保證所有的流量都可以被節(jié)點(diǎn)吸收（即不超過最大容量），然后將流量跑的最大距離限制到最小。
做法:SAP+二分+Floyd
1.首先預(yù)處理出任意兩點(diǎn)之間的最短路，二分最大距離mid;
2.將每個(gè)節(jié)點(diǎn)拆成i*2 i*2+1,i*2+1代表流出的點(diǎn)out[i]，i*2代表流進(jìn)的點(diǎn)in[i]，前者向后者連一條INF的邊。
3.建立超級(jí)源s，向每個(gè)點(diǎn)in[i],連一條當(dāng)前囤積流量的邊，每個(gè)點(diǎn)out[i]向超級(jí)匯t連一條最大容量的邊。
4.在floyd之后的數(shù)組中枚舉每?jī)蓚€(gè)點(diǎn)之間的最短距離，如果<=mid就建立一條out[i]->in[j]的邊
跑最大流，如果滿流，下降上界，否則提高下界。
這題做了收獲很大，學(xué)會(huì)了控制初始流量的方法和最后流量全部控制在容量?jī)?nèi)的方法。
另外就是拆點(diǎn)，分成兩個(gè)點(diǎn)之后，限制了只要進(jìn)來的流量就一定囤積在該點(diǎn)，由于這個(gè)點(diǎn)本身有初始流量，兩個(gè)點(diǎn)之間連的那條邊可以保證自己的流量也可以不流走。非常精彩的構(gòu)圖^_^
PS:順便說一下的是：雖然這個(gè)圖是無向圖，但是根據(jù)題意，走任意方向互不干擾，所以可以拆成兩條有向邊。一旦有流量經(jīng)過這條邊，那么流量不會(huì)流走，也就說明這個(gè)流量必須也只能走這么長(zhǎng)的距離，這個(gè)鎖定技巧很不錯(cuò)，于是就能二分了。。。
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;
}
題意：給出一個(gè)有源網(wǎng)絡(luò)流圖，每個(gè)點(diǎn)射出的流量有上界限制（除源點(diǎn)外），問是否可以在圖中找到匯點(diǎn)使得該網(wǎng)絡(luò)流圖滿流。
做法：感覺這題唯一的收獲就是學(xué)會(huì)了控制結(jié)點(diǎn)射出流量的方法，拆點(diǎn)，i->i`點(diǎn)連一條容量為限制數(shù)的邊，這樣就可以控制這個(gè)點(diǎn)流出的流量了。
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;
//入結(jié)點(diǎn)為2*i
//出結(jié)點(diǎn)為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;
}
摘要: 其實(shí)思路很簡(jiǎn)單，只是敲代碼的時(shí)候很容易敲錯(cuò)，MD，居然為了一個(gè)Pn>=n寫成了Pn>n NC地檢查了一個(gè)上午。如果是現(xiàn)場(chǎng)就悲劇了。。。
#include<iostream>#include<queue>#include<algorithm>using namespace std;#define INF 100...
閱讀全文
1Y。只是不明白為什么可以套兩個(gè)三分，不過從實(shí)際情況來看，在第一條直線上三分應(yīng)該也是符合凸函數(shù)性質(zhì)的。
#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為參數(shù)算出時(shí)間
{
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的基礎(chǔ)上得最小值
{
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;
}
二分法作為分治中最常見的方法，適用于單調(diào)函數(shù)，逼近求解某點(diǎn)的值。但當(dāng)函數(shù)是凸性函數(shù)時(shí)，二分法就無法適用，這時(shí)三分法就可以“大顯身手”～～
如圖，類似二分的定義Left和Right，mid = (Left + Right) / 2，midmid = (mid + Right) / 2; 如果mid靠近極值點(diǎn)，則Right = midmid；否則(即midmid靠近極值點(diǎn))，則Left = mid;
程序模版如下：
double Calc(Type a)
{
/* 根據(jù)題目的意思計(jì)算 */
}
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);
// 假設(shè)求解最大極值.
if (mid_area >= midmid_area) Right = midmid;
else Left = mid;
}
}
現(xiàn)根據(jù)幾道的OJ題目來分析三分法的具體實(shí)現(xiàn)。
buaa 1033 Easy Problem
http://acm.buaa.edu.cn/oj/problem_show.php?c=0&p=1033
題意為在一條線段上找到一點(diǎn)，與給定的Ｐ點(diǎn)距離最小。很明顯的凸性函數(shù)，用三分法來解決。
Calc函數(shù)即為求某點(diǎn)到P點(diǎn)的距離。
ZOJ 3203 Light Bulb
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203
如圖，人左右走動(dòng)，求影子L的最長(zhǎng)長(zhǎng)度。
根據(jù)圖，很容易發(fā)現(xiàn)當(dāng)燈，人的頭部和墻角成一條直線時(shí)(假設(shè)此時(shí)人站在A點(diǎn))，此時(shí)的長(zhǎng)度是影子全在地上的最長(zhǎng)長(zhǎng)度。當(dāng)人再向右走時(shí)，影子開始投影到墻上，當(dāng)人貼著墻，影子長(zhǎng)度即為人的高度。所以當(dāng)人從A點(diǎn)走到墻，函數(shù)是先遞增再遞減，為凸性函數(shù)，所以我們可以用三分法來求解。
下面只給出Calc函數(shù)，其他直接套模版即可。
double Calc(double x)
{
return (h * D - H * x) / (D - x) + x;
}
heru 5081 Turn the corner 08年哈爾濱regional網(wǎng)絡(luò)賽
http://acm.hrbeu.edu.cn/index.php?act=problem&id=1280
汽車拐彎問題，給定X, Y, l, d判斷是否能夠拐彎。首先當(dāng)X或者Y小于d，那么一定不能。
其次我們發(fā)現(xiàn)隨著角度θ的增大，最大高度ｈ先增長(zhǎng)后減小，即為凸性函數(shù)，可以用三分法來求解。
這里的Calc函數(shù)需要比較繁瑣的推倒公式：
s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
其中s為汽車最右邊的點(diǎn)離拐角的水平距離, h為里拐點(diǎn)最高的距離, θ范圍從0到90。
POJ 3301 Texas Trip
http://acm.pku.edu.cn/JudgeOnline/problem?id=3301
題意為給定n(n <= 30)個(gè)點(diǎn)，求出飽含這些點(diǎn)的面積最小的正方形。
有兩種解法，一種為逼近法，就是每次m分角度，求出最符合的角度，再繼續(xù)m分，如此進(jìn)行times次，即可求出較為精確的解。(m 大概取10, times取30即可)
第二種解法即為三分法，首先旋轉(zhuǎn)的角度只要在0到180度即可，超過180度跟前面的相同的。坐標(biāo)軸旋轉(zhuǎn)后，坐標(biāo)變換為：
X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;
至于這題的函數(shù)是否是凸性的，為什么是凸性的，我也無法給出準(zhǔn)確的證明，希望哪位路過的大牛指點(diǎn)一下～～
例題更新(2010.5.5)
hdu 3400 Line belt
http://acm.hdu.edu.cn/showproblem.php?pid=3400
典型的三分法，先三分第一條線段，找到一個(gè)點(diǎn)，然后根據(jù)這個(gè)點(diǎn)再三分第二條線段即可，想出三分的思路基本就可以過了。
對(duì)于求解一些實(shí)際問題，當(dāng)公式難以推導(dǎo)出來時(shí)，二分、三分法可以較為精確地求解出一些臨界值，且效率也是令人滿意的。
/* czyuan原創(chuàng)，轉(zhuǎn)載請(qǐng)注明出處。*/
轉(zhuǎn)自：
http://hi.baidu.com/czyuan_acm/blog/item/8cc45b1f30cefefde1fe0b7e.html
題意： 表示題意看不懂，不夠最后自己YY出來了。
簡(jiǎn)化一下題意可以如下描述：
給一個(gè)N*B的矩陣，N是牛的數(shù)量，B是牛舍的數(shù)量，每頭牛對(duì)應(yīng)一個(gè)牛舍序列（偏好是騙人的，不用管),每個(gè)牛舍有個(gè)容量C[i].
再給兩個(gè)指針l,r.指向矩陣的兩列(l<=r),現(xiàn)在規(guī)定l,r確定后，這些牛只能住進(jìn)[l,r]中間區(qū)域的牛舍，問是否可以安排?如果可以,問r-l+1最小值是多少。
做法：網(wǎng)絡(luò)流。這個(gè)枚舉的思想很巧妙，反正我自己是想不到。。。
如果某個(gè)[l,r]區(qū)間可以安排的話那么[l,r+1] to [l,b]肯定可以安排。所以應(yīng)該l++;
否則r++;
這題值得再研究下.
int n,b;
//牛[0,n-1]
//棚[n,n+b-1]
//超級(jí)源[n+b]
//超級(jí)匯[n+b+1]
//共n+b+2個(gè)結(jié)點(diǎn)
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個(gè)點(diǎn)的一個(gè)無向圖，在保證存在t條從1到n的不重復(fù)路徑（任意一條邊都不能重復(fù))的前提下，要使得這t條路徑上的最大的那條邊最小。
解法：二分t條路徑上的最大邊權(quán)，對(duì)原圖的每一條邊如果其<=mid,添加一條容量是1的邊（正反都加上），然后跑一遍最大流，如果流量>=t,說明可以安排。迭代得最小值即可。
PS:我一直以為無向圖不能拆成2條相反邊的，但是這個(gè)題用這個(gè)做法卻AC了。由于被那道two shortest題目影響，我覺得是不是也要先求出最短路徑樹然后把dis[i]+w[i][j]>=dis[j]的邊建起來，把無向邊轉(zhuǎn)化成有向邊來做，但是這樣卻wa了，不知道為什么。也許這個(gè)題恰好能拆邊吧。
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;
}
越來越感覺網(wǎng)絡(luò)流+二分還挺常見的啊，而且往往是要求一個(gè)最大的量最小的時(shí)候用。
題意：有K臺(tái)機(jī)器，C頭奶牛，他們之間的距離用一個(gè)鄰接矩陣表示，每臺(tái)機(jī)器能容納M頭奶牛喝奶。現(xiàn)在給這C頭奶牛分配機(jī)器，滿足兩個(gè)要求:
1.這C頭奶牛可以找到機(jī)器（這個(gè)條件由M限制)
2.C頭奶牛中走的路程最長(zhǎng)的奶牛 要讓他的路程盡量短。
問這個(gè)最長(zhǎng)距離的最小值（有點(diǎn)繞。。。）
做法：首先floyd一下，與處理處點(diǎn)對(duì)之間的最短路長(zhǎng)度。
二分距離，保存原圖中<=mid的邊，添加超級(jí)源匯，s到每頭牛建立容量是1的邊，每臺(tái)機(jī)器到t建立容量是M的邊，跑一遍最大流，如果滿流，說明C頭牛都可以在mid的限制條件下被分配。取距離最小值即可.
模板就不貼了，構(gòu)圖如下：
int mat[maxn][maxn];
int K,C,M;
int n;//記錄牛和機(jī)器的總數(shù)量
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個(gè)結(jié)點(diǎn)
//
for(int i=0;i<=t;i++)
adj[i]=NULL;
len=0;//重新構(gòu)圖
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:開始沒搞清楚題目干嘛給鄰接矩陣，那么多輸入都是沒用的東西。
不過倒是自然地幫你編了號(hào)。。。額。。。只要加個(gè)s,t，省事了。。。