【Poj2112】Optimal Milking

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

来源和评测点

USACO 2003 US Open
Poj2112
Caioj1119

题目

【题目大意】
FJ把K个挤奶机搬进了住着C头奶牛的牧场。
挤奶机的编号为1~K，奶牛的编号为K+1~K+C。
每头奶牛到每台挤奶机距离不同，每台挤奶机每天最多服务M头奶牛。
求一种分配方案, 使得走得最远的奶牛走过的距离最小化，输出此距离

重点句：
Cows can traverse several paths on the way to their milking machine. 路径
the distance the furthest-walking cow travels is minimized 走最多的牛的路程最小
【输入格式】
数据第1行是3个整数K，C，M
（1≤K≤30）（1≤C≤200）（1≤M≤15）
接下来是一个（K+C）×（K+C）的距离矩阵。
矩阵元素为正并不超200。距离为0表示两个点之间无边存在。
【输出格式】
输出一个整数，即走得最远的奶牛走过的距离的最小化值。
【输入样例】
2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0
【输出样例】
2

分析

网络流教程和题目分类参见：
【OI之路】03图论算法-4网络流
其他网络流题目参见：Tag-网络流

其实可以尝试着看看英文题

依旧是folyd，然后二分答案
(反正最终还是要到达挤奶机的)

构图：
从源点到牛建权值为1的边
牛到挤奶机建权值为1的边（当满足二分条件时）
挤奶机到汇点建权值为m的边

相比上一题Ombrophobic Bovines相当无聊，秒AC

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=310,MAXM=91000;
int mymin(int x,int y) {return x<y?x:y;}
struct pt
{
    int h;
    int hou;
}p[MAXN];
struct rod
{
    int y,c,g;
    int oth;
}e[MAXM];
int ln;
void ins(int x,int y,int c)
{
    ln++;
    e[ln].y=y;e[ln].c=c;
    e[ln].g=p[x].hou;p[x].hou=ln;
    
    ln++;
    e[ln].y=x;e[ln].c=0;
    e[ln].g=p[y].hou;p[y].hou=ln;
    
    e[ln].oth=ln-1;e[ln-1].oth=ln;
}
int st,ed;
int lst[MAXN];
bool bfs()
{
    for(int i=1;i<=ed;i++) p[i].h=0;
    
    int tou=1,wei=1;
    lst[1]=st;p[st].h=1;
    while(tou<=wei)
    {
        int x=lst[tou];
        for(int k=p[x].hou;k>0;k=e[k].g)
        {
            int y=e[k].y;
            if(p[y].h==0 and e[k].c>0)
            {
                p[y].h=p[x].h+1;
                lst[++wei]=y;
            }
        }
        tou++;
    }
    return p[ed].h>0;
}
int dfs(int x,int f)
{
    if(x==ed) return f;
    int t=0;
    for(int k=p[x].hou;k>0;k=e[k].g)
    {
        int y=e[k].y;
        if(p[y].h==p[x].h+1 and e[k].c>0 and t<f)
        {
            int tt=dfs(y,mymin(f-t,e[k].c));
            t+=tt;e[k].c-=tt;e[e[k].oth].c+=tt;
        }
    }
    if(t==0) p[x].h=0;
    return t;
}
//挤奶机的编号为1~K，奶牛的编号为K+1~K+C
int cst[MAXN][MAXN];
int nk,nc,m;
bool check(int mid)
{
    ln=0;for(int i=1;i<=ed;i++) p[i].hou=0;
    
    for(int i=1;i<=nc;i++) ins(st,i,1);
    for(int i=1;i<=nc;i++)
        for(int j=1;j<=nk;j++)
            if(cst[j][nk+i]<=mid)
                ins(i,nc+j,1);
    for(int j=1;j<=nk;j++) ins(nc+j,ed,m);
    
    int ans=0;
    while(bfs()) ans+=dfs(st,INF);
    return ans==nc;
}
int main()
{
    scanf("%d%d%d",&nk,&nc,&m);
    st=nc+nk+1,ed=nc+nk+2;
    int n=nk+nc;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int c;scanf("%d",&c);
            cst[i][j]=(c==0)?INF:c;
        }
    int l=0,r=0;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                int tt=cst[i][k]+cst[k][j];
                if(tt<cst[i][j]) cst[i][j]=tt;
                if(cst[i][j]!=INF and r<cst[i][j]) r=cst[i][j];
            }
    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",ans);
}

分析2

然鹅通过改进匈牙利算法实现多重二分图匹配
能大幅度加快速度，从而取代网络流
思路来自http://blog.csdn.net/leolin_/article/details/7195205

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
const int INF=0x3f3f3f3f;
const int MAXGN=300,MAXMN=50,MAXM=15000;
int hou[MAXGN];
struct rod
{
    int y,g;
}e[MAXM];
int ln;
void ins(int x,int y)
{
    ln++;e[ln].y=y;
    e[ln].g=hou[x];hou[x]=ln;
}
int gn,mn;
int mnum[MAXMN];
int match[MAXMN][20];
int ask[MAXMN];
int tnow;
int kk,cc,mm;
bool find_muniu(int x)
{
    for(int k=hou[x];k>0;k=e[k].g)
    {
        int y=e[k].y;
        if(ask[y]<tnow)
        {
            ask[y]=tnow;
            if(mnum[y]<mm)
            {
                match[y][++mnum[y]]=x;
                return 1;
            }
            else
            {
                for(int z=1;z<=mnum[y];z++)
                {
                    if(find_muniu( match[y][z] ))
                    {
                        match[y][z]=x;
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}
int cst[MAXGN+MAXMN][MAXGN+MAXMN];
bool check(int mid)
{
    ln=0;
    for(int i=1;i<=gn;i++)
    {
        hou[i]=0;
        for(int j=1;j<=mn;j++)
            if(cst[kk+i][j]<=mid)
                ins(i,j);
    }
    memset(ask,0,sizeof(ask));//debug
    memset(mnum,0,sizeof(mnum));//debug
    for(tnow=1;tnow<=gn;tnow++)
        if(find_muniu(tnow)==0) return 0;
    return 1;
}
int mx;
void folyd(int n)
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cst[i][j]=mymin(cst[i][k]+cst[k][j],cst[i][j]);
    mx=0;
    for(int i=1;i<=kk;i++)
        for(int j=1;j<=cc;j++)
            if(cst[i][j]>mx and cst[i][j]<INF) mx=cst[i][j];
}
int main()
{
    scanf("%d%d%d",&kk,&cc,&mm);
    for(int i=1;i<=kk+cc;i++)
        for(int j=1;j<=kk+cc;j++)
        {
            int t;scanf("%d",&t);
            cst[i][j]=(t==0)?INF:t;
        }
    folyd(kk+cc);
    
    gn=cc,mn=kk;
    int l=0,r=mx,ans=-1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans);
}
相关文章推荐

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址：http://zory.ink/posts/41bc.html
转载请注明出处，谢谢！