洛谷P2857[USACO06FEB]Steady Cow Assignment G
思路：
很巧妙的一道题。 很容易想到，将
S
S
S向牛
i
i
i连一条流量为
1
1
1的边，将牛棚
j
j
j向
T
T
T连一条流量为
B
j
B_j
Bj的边。但是
i
i
i和
j
j
j之间怎么连边才能使所要求的对于牛棚喜爱度的差值最小？ 我们假设差值为
x
x
x，随着
x
x
x的增大，牛棚自然就越容易分配。或者说，如果一个
x
x
x不能满足分配的要求的话，那么比这个
x
x
x更小的数就更不可能满足，因为随着
x
x
x的减少，
i
i
i与
j
j
j之间的连边就会减少。 我们就可以二分
x
x
x的值，然后枚举
i
∈
[
1
,
m
−
x
+
1
]
i\in[1,m-x+1]
i∈[1,m−x+1]。
a
p
,
q
a_{p,q}
ap,q表示第
p
p
p头牛第
q
q
q个喜欢的牛棚是多少。就可以将牛
p
p
p和牛棚
a
p
,
[
i
.
.
.
i
+
x
−
1
]
a_{p,[i...i+x-1]}
ap,[i...i+x−1]建一条流量为
1
1
1的边。 然后跑最大流判断流量是否能为
n
n
n，如果能，就表示存在一种分配方式使差值为
x
x
x的情况满足。
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define INF 1e18
const int N
=1e6+10;
const int M
=1e3+10;
const int mod
=1e9+7;
const int inf
=0x3f3f3f3f;
const int maxn
=0x3f3f3f3f;
const double eps
=1e-8;
const double pi
=acos(-1);
using namespace std
;
int a
[M
][M
],p
[M
];
struct edge
{
int u
,v
,w
;
}maze
[N
<<1];
int len
=1,head
[N
]={0};
int dep
[N
];
void add(int u
,int v
,int w
)
{
maze
[++len
]={head
[u
],v
,w
};
head
[u
]=len
;
}
void inc(int u
,int v
,int w
)
{
add(u
,v
,w
);
add(v
,u
,0);
}
int dfs(int u
,int f
,int t
)
{
int ans
=0,i
;
if(u
==t
)
return f
;
for(i
=head
[u
];i
&& f
;i
=maze
[i
].u
)
{
int v
=maze
[i
].v
,w
=maze
[i
].w
;
if(dep
[v
]==dep
[u
]+1 && w
)
{
int sum
=dfs(v
,min(f
,w
),t
);
maze
[i
].w
-=sum
;
maze
[i
^1].w
+=sum
;
f
-=sum
;
ans
+=sum
;
}
}
if(!ans
)
dep
[u
]=-2;
return ans
;
}
int bfs(int s
,int t
)
{
queue
<int> q
;
cl(dep
,0);
dep
[s
]=1;
q
.push(s
);
while(!q
.empty())
{
int u
=q
.front(),i
;
q
.pop();
for(i
=head
[u
];i
;i
=maze
[i
].u
)
{
int v
=maze
[i
].v
,w
=maze
[i
].w
;
if(w
&& !dep
[v
])
{
dep
[v
]=dep
[u
]+1;
q
.push(v
);
}
}
}
return dep
[t
];
}
int dinic(int s
,int t
)
{
int ans
=0;
while(bfs(s
,t
))
ans
+=dfs(s
,maxn
,t
);
return ans
;
}
int n
,m
,s
,t
;
int judge(int x
)
{
int i
,j
,k
;
for(i
=1;i
+x
-1<=m
;i
++)
{
cl(head
,0);
len
=1;
for(j
=1;j
<=n
;j
++)
inc(s
,j
,1);
for(j
=1;j
<=m
;j
++)
inc(j
+n
,t
,p
[j
]);
for(j
=1;j
<=n
;j
++)
for(k
=i
;k
<=i
+x
-1;k
++)
inc(j
,a
[j
][k
]+n
,1);
if(dinic(s
,t
)==n
)
return 1;
}
return 0;
}
int main()
{
ios
::sync_with_stdio(false);
cin
.tie(0);cout
.tie(0);
int i
,j
;
cin
>>n
>>m
;
for(i
=1;i
<=n
;i
++)
for(j
=1;j
<=m
;j
++)
cin
>>a
[i
][j
];
s
=0;
t
=n
+m
+1;;
for(i
=1;i
<=m
;i
++)
cin
>>p
[i
];
int l
=1,r
=m
,ans
;
while(l
<=r
)
{
int mid
=(l
+r
)/2;
if(judge(mid
))
{
ans
=mid
;
r
=mid
-1;
}
else
l
=mid
+1;
}
cout
<<ans
<<endl
;
return 0;
}
