POJ--2112--Optimal Milking【Floyd+Dinic+二分答案】

题意：有k个挤奶器。编号1~k，c头牛，编号k+1~k+c，每一个挤奶器最多能给m头牛挤奶，给你一个k+c的邻接矩阵。要求每头牛都能挤奶而且要求c头牛须要走的全部路程中的最大路程最小，求这个最小的路。

思路：

1. 先用floyd处理出多源最短路

2. 用二分枚举答案的可能。初始上限应该为（200+30）*200。可是我这么开T了，可能由于代码太挫，改到1000，卡着时间过了，仅仅能说poj数据弱了。后来看别人的代码。和我的做法一样可是用了邻接表。就能设上限为40000了。在二分中：

（1）构造容量网络，以0点为源点。到每头牛的容量为1。以n+1点为汇点。每一个挤奶器到汇点的容量为m，当然反过来也能够，由于源点和汇点的流量是相等的（等于c）。对于每头牛和每一个挤奶器之间的距离，假设比枚举的距离还大。则容量为0，否则容量为1。

（2）Dinic找出网络最大流，非常明显最大流最大是c，当最大流是c的时候是一种答案。但不一定是最优。更新二分上限。假设最大流没达到c，则更新下限。

这是做完POJ2391知道了Dinic优化。改进后的写法。优化了三个地方：容量网络改为邻接表、Dinic优化、二分上限从floyd中返回，157MS ，我原以为Dinic优化应该是效率提高的主要原因。把Dinic优化去掉单纯用邻接表。266MS。原来邻接表才是这道题效率提高的主要原因，可是Dinic优化还是非常实用的。

假设floyd再加个剪枝，能够跑110MS

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 200100

#define eps 1e-7

#define INF 0x7FFFFFFF

#define LLINF 0x7FFFFFFFFFFFFFFF

#define seed 131

#define mod 1000000007

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

struct node{

    int u,w,next;

}edge[MAXN];

int head[350],e[350][350];

int dist[350];

int cnt,n,m,k,c,src,sink;

void add_edge(int a,int b,int c){

    edge[cnt].u = b;

    edge[cnt].w = c;

    edge[cnt].next = head[a];

    head[a] = cnt++;

}

int floyd(){

    int i,j,k;

    int maxm = 0;

    for(k=1;k<=n;k++){

        for(i=1;i<=n;i++){

            if(e[i][k]==INF)    continue;

            for(j=1;j<=n;j++){

                if(e[k][j]!=INF&&e[i][k]+e[k][j]<e[i][j]){

                    e[i][j] = e[i][k] + e[k][j];

                    if(e[i][j]>maxm)    maxm = e[i][j];

                }

            }

        }

    }

    return maxm;

}

void build_graph(int minm){

    int i,j;

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

    cnt = 0;

    for(i=1;i<=k;i++){

        add_edge(i,n+1,m);

        add_edge(n+1,i,0);

    }

    for(i=k+1;i<=n;i++){

        add_edge(0,i,1);

        add_edge(i,0,0);

    }

    for(i=k+1;i<=n;i++){

        for(j=1;j<=k;j++){

            if(e[i][j]<=minm){

                add_edge(i,j,1);

                add_edge(j,i,0);

            }

        }

    }

}

int bfs(){

    int i,j;

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

    queue<int>q;

    q.push(0);

    dist[0] = 1;

    while(!q.empty()){

        int t = q.front();

        q.pop();

        for(i=head[t];i!=-1;i=edge[i].next){

            if(dist[edge[i].u]==-1&&edge[i].w){

                dist[edge[i].u] = dist[t] + 1;

                q.push(edge[i].u);

            }

        }

    }

    if(dist[n+1]!=-1)    return 1;

    else    return 0;

}

int dfs(int u,int delta){

    int i,j;

    int dd;

    if(u==n+1)  return delta;

    for(i=head[u];i!=-1;i=edge[i].next){

        if(dist[edge[i].u]==dist[u]+1&&edge[i].w&&(dd = dfs(edge[i].u,min(edge[i].w,delta)))){

            edge[i].w -= dd;

            edge[i^1].w += dd;

            return dd;

        }

    }

    dist[u] = -1;

    return 0;

}

int main(){

    int i,j;

    while(scanf("%d%d%d",&k,&c,&m)!=EOF){

        n = k + c;

        for(i=1;i<=n;i++){

            for(j=1;j<=n;j++){

                scanf("%d",&e[i][j]);

                if(e[i][j]==0)   e[i][j] = INF;

            }

        }

        int mid, l = 0,r=floyd();

        int sum,temp;

        while(l<r){

            mid = (l+r)/2;

            sum = 0;

            build_graph(mid);

            while(bfs()){

                while(1){

                    temp = dfs(0,INF);

                    if(!temp)   break;

                    sum += temp;

                }

            }

            if(sum>=c)  r = mid;

            else    l = mid + 1;

        }

        printf("%d\n",l);

    }

    return 0;

}

之前的写法，1875MS擦边过了。

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 50100

#define eps 1e-7

#define INF 0x7FFFFFFF

#define seed 131

#define mod 1000000007

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int edge[300][300],customer[300][300];

int vis[300],dist[300][300];

int n,m,k,c;

void floyd(){

    int i,j,k;

    for(k=1;k<=n;k++){

        for(i=1;i<=n;i++){

            for(j=1;j<=n;j++){

                if(edge[i][k]!=INF&&edge[k][j]!=INF&&edge[i][k]+edge[k][j]<edge[i][j])

                    edge[i][j] = edge[i][k] + edge[k][j];

            }

        }

    }

}

void build_graph(int minm){

    int i,j;

    memset(customer,0,sizeof(customer));

    for(i=1;i<=k;i++)   customer[i][n+1] = m;

    for(i=k+1;i<=n;i++) customer[0][i] = 1;

    for(i=k+1;i<=n;i++){

        for(j=1;j<=k;j++){

            if(edge[i][j]<=minm) customer[i][j] = 1;

        }

    }

}

int bfs(){

    int i,j;

    memset(vis,0,sizeof(vis));

    memset(dist,0,sizeof(dist));

    queue<int>q;

    q.push(0);

    vis[0] = 1;

    while(!q.empty()){

        int t = q.front();

        q.pop();

        for(i=0;i<=n+1;i++){

            if(!vis[i]&&customer[t][i]){

                vis[i] = 1;

                dist[t][i] = 1;

                q.push(i);

            }

        }

    }

    if(vis[n+1])    return 1;

    else    return 0;

}

int dfs(int u,int delta){

    int i,j,s;

    if(u==n+1)  return delta;

    s = delta;

    for(i=0;i<=n+1;i++){

        if(dist[u][i]){

            int dd = dfs(i,min(customer[u][i],delta));

            customer[u][i] -= dd;

            customer[i][u] += dd;

            delta -= dd;

        }

    }

    return s - delta;

}

int main(){

    int i,j;

    while(scanf("%d%d%d",&k,&c,&m)!=EOF){

        n = k + c;

        for(i=1;i<=n;i++){

            for(j=1;j<=n;j++){

                scanf("%d",&edge[i][j]);

                if(edge[i][j]==0)   edge[i][j] = INF;

            }

        }

        floyd();

        int mid, l = 0, r = 10000;

        int sum;

        while(l<r){

            mid = (l+r)/2;

            sum = 0;

            build_graph(mid);

            while(bfs())    sum += dfs(0,INF);

            if(sum==c)  r = mid;

            else    l = mid + 1;

        }

        printf("%d\n",l);

    }

    return 0;

}

巴特西

POJ--2112--Optimal Milking【Floyd+Dinic+二分答案】

最新文章

热门文章