为啥RE了
查看原帖
为啥RE了
529977
Soaring_light楼主2023/12/24 20:02

第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;
}
2023/12/24 20:02
加载中...