社区讨论

求助,为什么我这种拆点连边的方式会被m=1的#3号点卡掉

P2050[NOI2012] 美食节参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6tptyj
此快照首次捕获于
2025/11/20 10:40
4 个月前
此快照最后确认于
2025/11/20 10:40
4 个月前
查看原帖
除了#3的点都过了 查看数据后发现#3的m=1 自己看仍找不到问题
CPP
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define Min(_A,_B) (_A<_B?_A:_B)
const int maxn = 81007,inf=0x3f3f3f3f;
struct edge {
	int v, w, c, nxt;
}e[500007];
int head[maxn], eid = 0, d[maxn],s,
t,n,m,p[maxn],u,v,pre[maxn],incf[maxn],sp;
bool inq[maxn];
int g[41][101];
void insert(int u, int v, int c, int w) {
	e[eid].v = v; 
	e[eid].c = c; 
	e[eid].w = w; 
	e[eid].nxt = head[u];
	head[u]=eid++;
}
void addedge(int u, int v, int c, int w) {
	insert(u, v, c, w);
	insert(v, u, 0, -w);
}
void init() {
	memset(head, -1, sizeof(head));
	eid = 0;
}
/*动态加边的思路是 如果增广路流经x->t 与x相连的菜
表示厨师j做的倒数第x-n-(j-1)*p道菜
根据此题的构图
	厨师i做的第j道菜耗时g[j][i]
	第j+1道菜耗时g[j+1][i]+g[j][i]
	第j+2道菜耗时g[j+2][i]+g[j+1][i]+g[j][i]
	总时长为g[j][i]*3+g[j+1][i]*2+g[j+2][i]
	故我们设各个菜与S相连 容量为pi
	厨师与t相连 每个厨师j占的点编号范围为
	n+p*(j-1)+1到n+p*j
	即把每个厨师拆成至多p个点。
有T[x]<T[x+1] 如果没有连向x 就不加连向x+1的边
*/
bool spfa() {
	memset(d, inf, sizeof(d));
	memset(inq, false, sizeof(inq));
	memset(pre, -1, sizeof(pre));
	queue<int> q;q.push(s);
	d[s] = 0;inq[s] = true;incf[s] = inf;
	while (!q.empty()) {
		u = q.front(); q.pop();inq[u] = false;
		for (int i = head[u]; ~i; i = e[i].nxt) {
				if (e[i].c>0&&d[e[i].v] > d[u] + e[i].w) {
					v=e[i].v;
					d[v] = d[u] + e[i].w;pre[v] = i;
					incf[v] = Min(incf[u], e[i].c);
					if (!inq[v]) {	inq[v] = true;q.push(v);}
				}
		}
	}
	return pre[t]!=-1;
}
int ans = 0,x;
void cost_flow() {
	while(spfa()){
		for(int i=t;i!=s;i=e[pre[i]^1].v){
			e[pre[i]].c-=incf[t];
			e[pre[i]^1].c+=incf[t];
		}
		ans+=d[t]*incf[t];
		x=e[pre[t]^1].v;//增广路连向t的边(厨师拆出的点)
		//获取厨师编号j:由x=n+(j-1)*p+k知,
		//j=(x-n)/p+1
		//厨师现在是倒数第k道菜
		//k=(x-n)%p
		addedge(x+1,t,1,0);
		int a=(x+1-n)/sp+1,b=(x+1-n)%sp;
		//if(a<=1) continue;
		for(int i=1;i<=n;i++){
			addedge(i,x+1,1,g[i][a]*b);
		}
	}
}
inline int read(){
	int s=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') {s=s*10+c-'0';c=getchar();}
	return s*f;
}
int main(){
	n=read();m=read();
	s=0;
	init();
	for(int i=1;i<=n;i++){
		p[i]=read();sp+=p[i];
		addedge(s,i,p[i],0);//p[i]道菜匹配p[i]次
	}
	t=sp*m+n+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){	
			g[i][j]=read();
			//连接每个厨师做的倒数第一道菜
		}
	for(int j=1;j<=m;j++){
		x=n+(j-1)*sp+1;//厨师j做的倒数第1道菜与x连
		for(int i=1;i<=n;i++){
			addedge(i,x,1,g[i][j]);
		}
		addedge(x,t,1,0);
	}
	cost_flow();
	printf("%d",ans);
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...