奇怪的wa on #6~10代码求调,悬1关
  • 板块P1402 酒店之王
  • 楼主seve_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/5 20:25
  • 上次更新2024/7/5 22:51:37
查看原帖
奇怪的wa on #6~10代码求调,悬1关
668972
seve_楼主2024/7/5 20:25
#include<bits/stdc++.h>
using namespace std;
int An,Pn,Qn,n;
const int maxn = 1000;
const int inf = 2147483647;
struct edge{
	int to,next,val;
}e[maxn];
int dis[maxn],now[maxn],head[maxn];
int S,T;
int cnt = 1;
void addedge(int u,int v,int w){
	cnt++;
	e[cnt].to = v;
	e[cnt].val = w;
	e[cnt].next = head[u];
	head[u] = cnt;
	
	cnt++;//建立流量为0的反向边 
	e[cnt].to = u;
	e[cnt].val = 0;;
	e[cnt].next = head[v];
	head[v] = cnt;
}
int bfs(){//构造分层图 
	for(int i = 1;i <= maxn;i++) dis[i] = inf;
	queue<int> q;
	q.push(S);
	dis[S] = 0;
	now[S] = head[S];
	while(!q.empty()){
		int x = q.front();
		q.pop();//并不会返回弹出元素的值! 
		for(int i = head[x];i;i = e[i].next){
			int y = e[i].to;
			//cout<<y<<" "<<dis[y]<<endl;
			if(e[i].val>0&&dis[y]==inf){
				q.push(y);
				now[y] = head[y];//
				dis[y] = dis[x]+1;
				//cout<<y<<"a"<<t<<endl;
				if(y == T) return 1;//汇点直接返回 
			}
		}
	}
	return 0;
}
int dfs(int x,int sum){//sum是整条增广路对最大流的贡献
	if(x == T) return sum;//到汇点,dfs结束
	int k,res = 0;//k最小剩余流量
	for(int i = now[x];i&&sum;i=e[i].next){
		now[x] = i;
		int y = e[i].to;
		if(e[i].val>0&&(dis[y]==dis[x]+1)){
			k = dfs(y,min(sum,e[i].val));
			if(k == 0) dis[y] = inf;
			e[i].val -= k;//流过
			e[i^1].val += k;//处理反向边
			res+=k;//总流量 
			sum-=k; 
			 
		}
	} 
	return res;
}
int dinic(){// 1 1 0 0 0
	int ans = 0;
	while(bfs()){
		ans += dfs(S,inf);
	}
	return ans; 
}
bool room[maxn][maxn],dish[maxn][maxn],rd[maxn][maxn],edg[maxn][maxn];
int main(){
	cin>>An>>Pn>>Qn;//客人下标:2~An+1 房间1下标:An+2~An+Pn+1  房间2下标:An+Pn+2~An+2Pn+1  菜下标:An+2Pn+2~An+2Pn+Qn+1 汇点:An+2Pn+Qn+2 
	int tot; 
	S = 1,T = An+2*Pn+Qn+2;
	for(int i = 1;i <= An;i++){
		addedge(1,i+1,1);//源点向客人连边 
		cout<<1<<"a"<<i+1<<endl;
		n++;
	}
	for(int i = 1;i <= An;i++){
		for(int j = 1;j <= Pn;j++){
			bool flag;
			cin>>flag;
			room[i][j] = flag;
		}
	}
	for(int i = 1;i <= An;i++){
		for(int j = 1;j <= Qn;j++){
			bool flag;
			cin>>flag;
			dish[i][j] = flag;
		}
	}
	for(int i = 1;i <= An;i++){
		for(int j = 1;j <= Pn;j++){
			if(room[i][j]){
				if(!edg[i+1][An+j+1]){
					addedge(i+1,An+j+1,1);
					edg[i+1][An+j+1] = true;
					cout<<i+1<<"b"<<An+j+1<<endl;
				}
				if(!edg[An+j+1][An+Pn+j+1]){
					addedge(An+j+1,An+Pn+j+1,1);
					cout<<An+j+1<<"b"<<An+Pn+j+1<<endl;
					edg[An+j+1][An+Pn+j+1] = true;
				}
				
				
			}
		}
	}
	for(int i = 1;i <= An;i++){
		for(int j = 1;j <= Qn;j++){
			if(dish[i][j]){
				for(int k = 1;k <= Pn;k++){
					if(room[i][k]){
						if(!edg[An+Pn+k+1][An+2*Pn+j+1]){
							addedge(An+Pn+k+1,An+2*Pn+j+1,1);//Pn->Qn
							cout<<An+Pn+k+1<<"c"<<An+2*Pn+j+1<<endl;
							edg[An+Pn+k+1][An+2*Pn+j+1] = true;
						}
						if(!edg[An+2*Pn+j+1][An+2*Pn+Qn+2]){
							addedge(An+2*Pn+j+1,An+2*Pn+Qn+2,1);
							cout<<An+2*Pn+j+1<<"c"<<An+2*Pn+Qn+2<<endl;
							edg[An+2*Pn+j+1][An+2*Pn+Qn+2] = true;
						}
					}
				}
			}
		}
	}
	cout<<dinic()<<endl;
}
2024/7/5 20:25
加载中...