首页 > 代码库 > poj Budget
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; }
poj Budget
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。