这样写建模的代码哪里错了啊。。。
  • 板块P1402 酒店之王
  • 楼主sysss
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/5/26 22:38
  • 上次更新2023/10/28 00:34:05
查看原帖
这样写建模的代码哪里错了啊。。。
270897
sysss楼主2022/5/26 22:38

如题,我这题的思路和题解一样,都是把人放在中间拆成两个点,dinic代码也过了模板,但是样例都跑不过 死循环

#include <stdio.h>
#include <vector>
#include <queue>
#define MAXN 500
using namespace std;

struct edge
{
	int u,v,w;
	edge()
	{
	}
	edge(int from,int to,int weight)
	{
		u = from,v = to,w = weight;
	}
};

vector<int> G[MAXN];

vector<edge> E;

int s,t;

int n,p,q;

void AddEdge(int u,int v,int w)
{
	E.push_back(edge(u,v,w));
	E.push_back(edge(v,u,0));
	G[u].push_back(E.size() - 2);
	G[v].push_back(E.size() - 1);
}

int cur[MAXN],dep[MAXN],inq[MAXN];


queue<int> bq;
bool bfs()
{
	for(int i = 0; i <= n; i++)
	{
		cur[i] = 0,dep[i] = 0,inq[i] = 0;
	}
	inq[s] = 1;
	dep[s] = 1;
	bq.push(s);
	while(!bq.empty())
	{
		int u = bq.front();
		bq.pop();
		for(int i = 0; i < G[u].size(); i++)
		{
			edge & e = E[G[u][i]];
			if(!inq[e.v] && e.w)
			{
				inq[e.v] = 1;
				dep[e.v] = dep[u] + 1;
				bq.push(e.v);
			}
		}
	}
	if(inq[t])
	return 1;
	return 0;
}

int maxFlow;

int dfs(int u,int flow)
{
	if(u == t)
	{
		maxFlow += flow;
		return flow;
	}
	int used = 0,rlow = 0;
	for(int i = cur[u]; i < G[u].size(); i++)
	{
		cur[u] = i;
		edge & e = E[G[u][i]];
		edge & re = E[G[u][i] ^ 1];
		if(e.w && dep[e.v] == dep[u] + 1)
		{
			if(rlow = dfs(e.v,min(flow - used,e.w)))
			{
				used += rlow;
				e.w -= rlow,re.w += rlow;
				if(used == flow)
				break;
			}
		}
	}
	return used; 
}

int dinic()
{
	while(bfs())
	{
		dfs(s,2147483647);
	}
	return maxFlow;
}

//第n位客人的节点编号 第n位的右边的一个点是cus[n + 1] 
int cus[MAXN];


int dish[MAXN],room[MAXN];


int nnt = 1;//nodeCnt

int main(void)
{
	
	scanf("%d%d%d",&n,&p,&q);
	for(int i = 1; i <= n; i++)
	{
		cus[i] = nnt;
		AddEdge(nnt,nnt + 1,1);
		nnt += 2;
	}
	
	for(int i = 1; i <= p; i++)
	{
		room[i] = nnt;
		nnt++;
	}
	
	for(int i = 1; i <= q; i++)
	{
		dish[i] = nnt;
		nnt++;
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= p; j++)
		{
			int x;
			scanf("%d",&x);
			if(x == 1)
			{
				AddEdge(room[j],cus[i],1);
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= q; j++)
		{
			int x;
			scanf("%d",&x);
			if(x == 1)
			{
				AddEdge(cus[i] + 1,dish[j],1);
			}
		}
	}
	s = nnt;
	nnt++;
	t = nnt;
	nnt++;
	for(int i = 1; i <= p; i++)
	{
		AddEdge(s,room[i],1);
	}
	for(int i = 1; i <= q; i++)
	{
		AddEdge(dish[i],t,1);
	}
	
	printf("%d",dinic());
}
2022/5/26 22:38
加载中...