3130: [Sdoi2013]費用流

Time Limit:?10 Sec??Memory Limit:?128 MBSec??Special Judge
Submit:?960??Solved:?505
[Submit][Status][Discuss]

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 的費用全用到流量最大的那條邊上
• 也就是說要讓最大流量的邊最小
• 二分邊的最大流看，檢查是否還能求得同樣大小的最大流
• 注意要實數二分，不能整數二分

最大流本身是一定的整數，但是為滿足最優解，某一條邊的流量可以是實數。所以這題是實數網絡流！

實數二分好坑.........不要m+-1，不要保留一個ans，只是簡單的二分l和r行了，最后取那一個都行

// // main.cpp // sdoi2003費用流 // // Created by Candy on 25/11/2016. // Copyright ? 2016 Candy. All rights reserved. // #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=105,M=1005,INF=1e9; const double eps=1e-5; int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}return x*f; } int n,m,p,u,v,c,s,t; struct data{int u,v,c; }a[M]; struct edge{int v,ne;double c,f; }e[M<<1]; int h[N],cnt=0; inline void ins(int u,int v,double c){cnt++;e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt;cnt++;e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt; } void build(double mid){cnt=0;memset(h,0,sizeof(h));for(int i=1;i<=m;i++) ins(a[i].u,a[i].v,min((double)a[i].c,mid)); } int cur[N]; int d[N],vis[N],q[N],head,tail; bool bfs(){memset(vis,0,sizeof(vis));memset(d,0,sizeof(d));head=tail=1;d[s]=0;vis[s]=1;q[tail++]=s;while(head!=tail){int u=q[head++];for(int i=h[u];i;i=e[i].ne){int v=e[i].v;if(!vis[v]&&e[i].c>e[i].f){d[v]=d[u]+1;vis[v]=1;q[tail++]=v;if(v==t) return 1;}}}return 0; }double dfs(int u,double a){if(u==t||a==0) return a;double flow=0,f;for(int &i=cur[u];i;i=e[i].ne){int v=e[i].v;if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){flow+=f;e[i].f+=f;e[((i-1)^1)+1].f-=f;a-=f;if(a==0) break;}}return flow; } double dinic(){double flow=0;while(bfs()){for(int i=1;i<=n;i++) cur[i]=h[i];flow+=dfs(s,INF);}return flow; } int main(int argc, const char * argv[]) {n=read();m=read();p=read();s=1;t=n;double l=0,r=0;for(int i=1;i<=m;i++){a[i].u=read(),a[i].v=read(),a[i].c=read();ins(a[i].u,a[i].v,a[i].c);r=max(r,(double)a[i].c);}//r+=eps;double old=dinic();while(r-l>eps){double mid=(l+r)*0.5;//printf("%f %f\n",l,r); build(mid);double mx=dinic();if(fabs(mx-old)<eps) r=mid;else l=mid;}printf("%d\n%.4f",(int)old,l*p);return 0; }

?

?

?

?

轉載于:https://www.cnblogs.com/candy99/p/6103372.html

總結

以上是生活随笔為你收集整理的BZOJ3130: [Sdoi2013]费用流[最大流 实数二分]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。