社区讨论
求助,为什么我这种拆点连边的方式会被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 条回复,欢迎继续交流。
正在加载回复...