第4,5,6个点一直RE
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
const int inf = 1e9 + 114514;
int n,b,cur[maxn],head[maxn],dis[maxn],s,t,cnt = 1,like[205][25],f[30];
struct node{
int val,to,nxt;
}edge[100005];
void add_edge(int u,int v,int w){
edge[++cnt] = (node){w,v,head[u]};
head[u] = cnt;
}
bool bfs(){
for(int i = 0;i <= t;i++){
dis[i] = inf;cur[i] = head[i];
}
dis[s] = 0;
queue<int>q;q.push(s);
while(!q.empty()){
int k = q.front();q.pop();
for(int i = head[k];i;i = edge[i].nxt){
int now = edge[i].to;
if(dis[now] == inf && edge[i].val > 0){
q.push(now);
dis[now] = dis[k] + 1;
if(now == t)return true;
}
}
}
return false;
}
int dfs(int x,int flow){
if(x == t)return flow;
int res = 0,k;
for(int i = cur[x];i && flow;i = edge[i].nxt){
int now = edge[i].to;cur[x] = i;
if(dis[now] == dis[x] + 1 && edge[i].val > 0){
k = dfs(now,min(edge[i].val,flow));
res += k;flow -= k;
edge[i].val -= k;edge[i^1].val += k;
}
}
return res;
}
int dinic(){
int ans = 0;
while(bfs())
ans += dfs(s,inf);
return ans;
}
bool check(int x){
for(int k = 1;k + x - 1 <= b;k++){
memset(head,0,sizeof(head));
for(int i = 1;i <= n;i++){
add_edge(s,i,1);
add_edge(i,s,0);
}
for(int j = 1;j <= b;j++){
add_edge(j + n,t,f[j]);
add_edge(t,j + n,0);
}
for(int i = 1;i <= n;i++)
for(int j = k;j <= k + x - 1;j++){
add_edge(i,like[i][j] + n,1);
add_edge(like[i][j] + n,i,0);
}
if(dinic() == n)return 1;
}
return 0;
}
int main(){
// freopen("P2857_4.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>b;
s = 0;t = n + b + 1;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= b;j++)
cin>>like[i][j];
}
for(int i = 1;i <= b;i++)cin>>f[i];
int l = 1,r = b,mid,ans;
while(l <= r){
mid = (l + r)>>1;
if(check(mid)){
ans = mid;r = mid - 1;
}else l = mid + 1;
}
cout<<ans;
}