#
這提相當經典啊，這題相當猥瑣啊。。。。
無向圖中給出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，省事了。。。