poj Budget

时间:2023-03-08 19:49:30
poj  Budget

Budget

建图好题。不知道为什么提交一直TLE。

然后。该了几次,看了别人的普通网络流都过了。

我觉得可能是卡DINIC的某些部分吧。这题就是一道普通的上下界最小流。

建图麻烦,所以说一下建图吧。

建图能够象方格取数的方法一样,把行列拆了。然后最后让行总和或列总和等于题目的要求。这样在满足一下题目的上下界要求后图就建好了。跑两边最大流就Ok了。

由于,一直TLE所以不给出完整代码。仅仅给出建图过程。囧。。。

int main()
{
int T;
scanf("%d\n",&T);
while(T--){
char ope[5];
int x,y,c; scanf("%d%d\n",&N,&M); init();
memset(in,0,sizeof(in)); for(int i = 1;i <= N;++i){
for(int j = 1;j <= M;++j){
B[i][j] = 0;
C[i][j] = INF;
}
} for(int i = 1;i <= N;++i){ //行
scanf("%d",&c); addEdge(ss,i,0);
in[ss] -= c;
in[i] += c;
} for(int j = 1;j <= M;++j){ //列
scanf("%d",&c); addEdge(j+N,tt,0);
in[j + N] -= c;
in[tt] += c;
} int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d%s%d",&x,&y,ope,&c);
if(c < 0){
flag = true;
}
int x1,x2,y1,y2;
x1 = x2 = x;
y1 = y2 = y;
if(!x) x1 = 1,x2 = N;
if(!y) y1 = 1,y2 = M;
for(int i = x1;i <= x2;++i){
for(int j = y1;j <= y2;++j){
if(ope[0] == '=')
B[i][j] = C[i][j] = c;
else if(ope[0] == '>')
B[i][j] = max(B[i][j],c + 1);
else
C[i][j] = min(C[i][j],c - 1);
if(C[i][j] < B[i][j])
flag = false;
}
}
} if(flag){
puts("IMPOSSIBLE");
if(T)puts("");
continue;
} //建图
for(int i = 1;i <= N;++i){
for(int j = 1;j <= M;++j){
addEdge(i,j + N,C[i][j] - B[i][j]);
in[i] -= B[i][j];
in[j+N] += B[i][j];
}
} int sum = 0;
for(int i = 1;i <= tt;++i){
if(in[i] > 0){
sum += in[i];
addEdge(src,i,in[i]);
}
if(in[i] < 0){
addEdge(i,sink,-in[i]);
}
} addEdge(tt,ss,INF); ///!!!!!!!!!! tt --> ss 不要在粗心了!!! T_T
int flow = maxFlow(src,sink); if(flow != sum){
puts("IMPOSSIBLE");
} else {
maxFlow(src,sink);
}
if(T)puts("");
}
return 0;
}