Codeforces 653 D. Delivery Bears

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://codeforces.com/problemset/problem/653/D

题目翻译

有一张 n 个点 m 条边 & 每条边流量为 Ai 的网络，现在要求增广 n 次每次增广流量相同，求最大可行流。

题解

首先我们发现，如果我们每条边设置的固定增广流量越大，那么增广次数就越少，反之反之。
所以我们二分固定增广流量，计算最大增广次数，顺便统计答案。
P.S. Hack数据可精度+爆Int

代码

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
struct Dinic{
    const static int Maxn=50;
    const static int Maxm=500;
    const static int Inf=2100000000;
    int head[Maxn+5];
    int cur[Maxn+5];
    struct Edge{
        int v,nxt;
        int f;
        double ff;
        Edge(){}
        Edge(int v0,int n0,double f0){
            v=v0;
            nxt=n0;
            ff=f=f0;
        }
    };
    Edge e[Maxm*2+5];
    int nume;
    inline void init(){
        nume=1;
        memset(head,0,sizeof(head));
    }
    inline void reset(double nowWeight,int maxFlow){
        for (int i=1;i<=nume;i++){
            e[i].f=min((long long)maxFlow,(long long)(e[i].ff/nowWeight));
            //printf("%d\n",(long long)(e[i].ff/nowWeight));
        }
    }
    inline void insertEdge(int u,int v,double f){
        e[++nume]=Edge(v,head[u],f);
        head[u]=nume;
    }
    inline void addEdge(int u,int v,double f){
        insertEdge(u,v,f);
        insertEdge(v,u,0);
    }
    int dist[Maxn+5];
    queue<int> que;
    int src,sink;
    inline bool bfs(){
        while(!que.empty())que.pop();
        memset(dist,-1,sizeof(dist));
        dist[src]=0;
        que.push(src);
        while(!que.empty()){
            int now=que.front();
            que.pop();
            for (int i=head[now];i;i=e[i].nxt){
                if (e[i].f>0 && dist[e[i].v]==-1){
                    dist[e[i].v]=dist[now]+1;
                    que.push(e[i].v);
                }
            }
        }
        return dist[sink]!=-1;
    }
    int dfs(int x,int delta){
        if (x==sink){
            return delta;
        }else{
            int ret=0;
            for (int &i=cur[x];i;i=e[i].nxt){
                if (e[i].f>0 && dist[e[i].v]==dist[x]+1){
                    int ddelta=dfs(e[i].v,min(e[i].f,delta));
                    e[i].f-=ddelta;
                    e[i^1].f+=ddelta;
                    delta-=ddelta;
                    ret+=ddelta;
                }
            }
            return ret;
        }
    }
    inline int Max_Flow(int src0,int sink0){
        src=src0;
        sink=sink0;
        int ret=0;
        while(bfs()){
            memcpy(cur,head,sizeof(head));
            ret+=dfs(src,Inf);
            //printf("%.10lf\n",ret);
        }
        return ret;
    }
};
Dinic dinic;
const double EPS=1e-12;
int n,m,x;
double left,right,Ans;
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&x);
    //printf("%d %d %d\n",n,m,x);
    dinic.init();
    for (int i=1;i<=m;i++){
        int x,y,f;
        scanf("%d%d%d",&x,&y,&f);
        dinic.addEdge(x,y,(double)f);
    }
    int maxFlow=dinic.Max_Flow(1,n);
    left=0,right=(double)maxFlow/(double)x;
    //printf("Right = %.10lf\n",right);
    while(right-left>EPS){
        double mid=(left+right)/2.0;
        dinic.reset(mid,(double)maxFlow/mid+1);
        int bear=dinic.Max_Flow(1,n);
        //printf("%.10lf %d\n",mid,bear);
        if (bear>=x){
            Ans = max(Ans , (double)x * mid);
            left=mid+EPS;
        }else{
            right=mid-EPS;
        }
    }
    printf("%.10lf\n",Ans);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

struct Dinic{

const static int Maxn=50;

const static int Maxm=500;

const static int Inf=2100000000;

int head[Maxn+5];

int cur[Maxn+5];

struct Edge{

int v,nxt;

int f;

double ff;

Edge(){}

Edge(int v0,int n0,double f0){

v=v0;

nxt=n0;

ff=f=f0;

}

};

Edge e[Maxm*2+5];

int nume;

inline void init(){

nume=1;

memset(head,0,sizeof(head));

}

inline void reset(double nowWeight,int maxFlow){

for (int i=1;i<=nume;i++){

e[i].f=min((long long)maxFlow,(long long)(e[i].ff/nowWeight));

//printf("%d\n",(long long)(e[i].ff/nowWeight));

}

inline void insertEdge(int u,int v,double f){

e[++nume]=Edge(v,head[u],f);

head[u]=nume;

}

inline void addEdge(int u,int v,double f){

insertEdge(u,v,f);

insertEdge(v,u,0);

}

int dist[Maxn+5];

queue<int> que;

int src,sink;

inline bool bfs(){

while(!que.empty())que.pop();

memset(dist,-1,sizeof(dist));

dist[src]=0;

que.push(src);

while(!que.empty()){

int now=que.front();

que.pop();

for (int i=head[now];i;i=e[i].nxt){

if (e[i].f>0 && dist[e[i].v]==-1){

dist[e[i].v]=dist[now]+1;

que.push(e[i].v);

}

return dist[sink]!=-1;

}

int dfs(int x,int delta){

if (x==sink){

return delta;

}else{

int ret=0;

for (int &i=cur[x];i;i=e[i].nxt){

if (e[i].f>0 && dist[e[i].v]==dist[x]+1){

int ddelta=dfs(e[i].v,min(e[i].f,delta));

e[i].f-=ddelta;

e[i^1].f+=ddelta;

delta-=ddelta;

ret+=ddelta;

}

return ret;

}

inline int Max_Flow(int src0,int sink0){

src=src0;

sink=sink0;

int ret=0;

while(bfs()){

memcpy(cur,head,sizeof(head));

ret+=dfs(src,Inf);

//printf("%.10lf\n",ret);

}

return ret;

}

};

Dinic dinic;

const double EPS=1e-12;

int n,m,x;

double left,right,Ans;

int main(){

//freopen("in.txt","r",stdin);

scanf("%d%d%d",&n,&m,&x);

//printf("%d %d %d\n",n,m,x);

dinic.init();

for (int i=1;i<=m;i++){

int x,y,f;

scanf("%d%d%d",&x,&y,&f);

dinic.addEdge(x,y,(double)f);

}

int maxFlow=dinic.Max_Flow(1,n);

left=0,right=(double)maxFlow/(double)x;

//printf("Right = %.10lf\n",right);

while(right-left>EPS){

double mid=(left+right)/2.0;

dinic.reset(mid,(double)maxFlow/mid+1);

int bear=dinic.Max_Flow(1,n);

//printf("%.10lf %d\n",mid,bear);

if (bear>=x){

Ans = max(Ans , (double)x * mid);

left=mid+EPS;

}else{

right=mid-EPS;

}

printf("%.10lf\n",Ans);

return 0;

}

WNJXYKの博客

喂你脚下有坑