bzoj3130【SDOI2013】費用流
Description
Alice和Bob在圖論課程上學習了最大流和最小費用最大流的相關知識。
最大流問題：給定一張有向圖表示運輸網絡，一個源點S和一個匯點T，每條邊都有最大流量。一個合法的網絡流方案必須滿足：(1)每條邊的實際流量都不超過其最大流量且非負；(2)除了源點S和匯點T之外，對於其余所有點，都滿足該點總流入流量等於該點總流出流量；而S點的淨流出流量等於T點的淨流入流量，這個值也即該網絡流方案的總運輸量。最大流問題就是對於給定的運輸網絡，求總運輸量最大的網絡流方案。
上圖表示了一個最大流問題。對於每條邊，右邊的數代表該邊的最大流量，左邊的數代表在最優解中，該邊的實際流量。需要注意到，一個最大流問題的解可能不是唯一的。 對於一張給定的運輸網絡，Alice先確定一個最大流，如果有多種解，Alice可以任選一種；之後Bob在每條邊上分配單位花費（單位花費必須是非負實數），要求所有邊的單位花費之和等於P。總費用等於每一條邊的實際流量乘以該邊的單位花費。需要注意到，Bob在分配單位花費之前，已經知道Alice所給出的最大流方案。現茌Alice希望總費用盡量小，而Bob希望總費用盡量大。我們想知道，如果兩個人都執行最優策略，最大流的值和總費用分別為多少。
Input
第一行三個整數N，M，P。N表示給定運輸網絡中節點的數量，M表示有向邊的數量，P的含義見問題描述部分。為了簡化問題，我們假設源點S是點1，匯點T是點N。
接下來M行，每行三個整數A，B，C，表示有一條從點A到點B的有向邊，其最大流量是C。
Output
第一行一個整數，表示最大流的值。
第二行一個實數，表示總費用。建議選手輸出四位以上小數。
Sample Input
3 2 1
1 2 10
2 3 15
Sample Output
10
10.0000
HINT
【樣例說明】
對於Alice，最大流的方案是固定的。兩條邊的實際流量都為10。
對於Bob，給第一條邊分配0.5的費用，第二條邊分配0.5的費用。總費用
為：10*0.5+10*0.5=10。可以證明不存在總費用更大的分配方案。
【數據規模和約定】
對於20%的測試數據：所有有向邊的最大流量都是1。
對於100%的測試數據：N < = 100，M < = 1000。
對於l00%的測試數據：所有點的編號在I..N范圍內。1 < = 每條邊的最大流
量 < = 50000。1 < = P < = 10。給定運輸網絡中不會有起點和終點相同的邊。
首先，我們站在Bob的角度，如果知道每個邊的流量，單位花費如何分配才能使總花費最大？
顯然只要讓最大邊的單位花費為p，其余邊為0。
問題轉化為：在最大流的條件下，使流量最大的邊最小。
最大值最小問題，二分解決。二分一個mid，將所有邊的邊權改為min(v,mid)，判斷能否流出最大流。
注意實數二分與整數二分的一些一些區別。
#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 105
#define maxm 1005
#define inf 1000000000
#define eps 1e-10
using namespace std;
int n,m,p,s,t,cnt,head[maxn],cur[maxn],dis[maxn];
double ans,mxf;
struct edge_type{int next,to;double v;}e[maxm*2];
struct data{int x,y;double v;}a[maxm];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add_edge(int x,int y,double z)
{
e[++cnt]=(edge_type){head[x],y,z};head[x]=cnt;
e[++cnt]=(edge_type){head[y],x,0};head[y]=cnt;
}
inline bool bfs()
{
queue q;
memset(dis,-1,sizeof(dis));
dis[s]=0;q.push(s);
while (!q.empty())
{
int x=q.front();q.pop();
if (x==t) return true;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (e[i].v>eps&&dis[y]==-1)
{
dis[y]=dis[x]+1;
q.push(y);
}
}
}
return false;
}
inline double dfs(int x,double f)
{
if (x==t) return f;
double sum=0,tmp;
for(int &i=cur[x];i;i=e[i].next)
{
int y=e[i].to;
if (e[i].v>eps&&dis[y]==dis[x]+1)
{
tmp=dfs(y,min(e[i].v,f-sum));
e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp;
if (fabs(f-sum)<=eps) return f;
}
}
if (sum1e-6)
{
mid=(l+r)/2;
memset(head,0,sizeof(head));cnt=1;
F(i,1,m) add_edge(a[i].x,a[i].y,min(a[i].v,mid));
dinic();
if (fabs(ans-mxf)
