首页 > 代码库 > poj2396 Budget 有源汇上下界可行流
poj2396 Budget 有源汇上下界可行流
/** 题目:poj2396 Budget 链接:http://poj.org/problem?id=2396 题意: 给定一个n*m矩阵,矩阵元素未知。已知第1~n行的元素和,第1~m列的元素和。以及元素的一些数据范围。 求一个可行的矩阵。 思路: 联想到以前没有下届的做法,用一个s连接所有的行节点,容量为该行的和,所有的列节点连接t,容量为该列的和。 所有的行节点连接所有的列节点,容量为无穷,然后求s到t的最大流。如果从s出发的弧都是满载的,那么有解。 所有行到所有列的flow为对应的行列位置元素值。 存在下界: 将其转化为求无源汇有上下界的可行流。由于s->t为源汇,从t连一条到s,容量为无穷的弧, 给s到所有的行节点的边添加下界,值和上界相同。给所有列到t的边添加下界,值和上界相同。 这样就变成无源汇有上下界的图。 然后就是对这个新的图用求无源汇有上下界的可行流的做法。 增加附加点S,T。将有上下界的边变成下界为0,上界为up-down的边。为了每个节点进出流量相等,比较每一个节点的所有入度下界和的大小与所有出度下界和的大小。 如果in[i]>out[i],那么从S到i连一条下界为0,上界为in[i]-out[i]的附加边。 如果in[i]<out[i],那么从i到T连一条下界为0,上界为out[i]-in[i]的附加边。 求S-T最大流。如果所有的附加边都是满载,那么有可行流。此时的可行流即是本题矩阵结果。 ps:本题要注意有矛盾的数据。可以直接得出结果。 */ #include<iostream> #include<cstring> #include<vector> #include<map> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int INF = 0x3f3f3f3f; typedef long long LL; const int N = 240;///n+m=220 int in[N]; int out[N]; int flag; struct node { int up, down; } a[N][22]; struct Edge{ int from, to, cap, flow; Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} }; struct Dinic{ int n, m, s, t; vector<Edge> edges; vector<int> G[N]; bool vis[N]; int d[N]; int cur[N]; void init(int n) { this->n = n; for(int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap) { edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof vis); queue<int> Q; Q.push(s); d[s] = 0; vis[s] = 1; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge &e = edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to] = 1; d[e.to] = d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if(x==t||a==0) return a; int flow = 0, f; for(int &i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a==0) break; } } return flow; } int Maxflow(int s,int t) { this->s = s, this->t = t; int flow = 0; while(BFS()) { memset(cur, 0, sizeof cur); flow += DFS(s,INF); } return flow; } bool check(int r,int c)///判断附加边是否都满载。 { for(int i = 2*(r+c)+2*r*c+2; i < edges.size(); i+=2){ if(edges[i].cap!=edges[i].flow) return false; } return true; } void print(int r,int c) { if(check(r,c)==false){ printf("IMPOSSIBLE\n"); return ; } int col = 0, row = 1; for(int i = 2*(r+c); i < 2*(r+c)+2*r*c; i+=2){ col++; if(col==c){ printf("%d\n",edges[i].flow+a[row][col].down); col = 0; row++; }else { printf("%d ",edges[i].flow+a[row][col].down); } } } }; void ok(int x,int y,int w) { if(a[x][y].up<w||a[x][y].down>w) flag = 1; } int main() { int n, m, T, r, c; scanf("%d",&T); while(T--){ scanf("%d%d",&r,&c); int s = 0, t = r+c+1; Dinic dinic; dinic.init(t+2); memset(in, 0, sizeof in); memset(out, 0, sizeof out); flag = 0; int cap; for(int i = 1; i <= r; i++){ scanf("%d",&cap); dinic.AddEdge(s,i,0); out[s]+=cap; in[i] += cap; } for(int i = 1; i <= c; i++){ scanf("%d",&cap); dinic.AddEdge(r+i,t,0); out[r+i] += cap; in[t] += cap; } scanf("%d",&m); int x, y, w; char op[2]; for(int i = 0; i <= r; i++){ for(int j = 0; j <= c; j++){ a[i][j].down = 0; a[i][j].up = INF; } } for(int i = 0; i < m; i++){ scanf("%d%d%s%d",&x,&y,op,&w); if(x!=0&&y!=0){ if(op[0]==‘=‘){ ok(x,y,w); a[x][y].up = a[x][y].down = w; } if(op[0]==‘>‘){ a[x][y].down = max(a[x][y].down,w+1); } if(op[0]==‘<‘){ a[x][y].up = min(a[x][y].up,w-1); } }else if(x==0&&y==0){ for(int i = 1; i <= r; i++){ for(int j = 1; j <= c; j++){ if(op[0]==‘=‘){ ok(x,y,w); a[i][j].up = a[i][j].down = w; } if(op[0]==‘>‘){ a[i][j].down = max(a[i][j].down,w+1); } if(op[0]==‘<‘){ a[i][j].up = min(a[i][j].up,w-1); } } } }else if(x==0){ if(op[0]==‘=‘){ for(int i = 1; i <= r; i++){ ok(x,y,w); a[i][y].up = a[i][y].down = w; } } if(op[0]==‘>‘){ for(int i = 1; i <= r; i++){ a[i][y].down = max(a[i][y].down,w+1); } } if(op[0]==‘<‘){ for(int i = 1; i <= r; i++){ a[i][y].up = min(a[i][y].up,w-1); } } }else if(y==0){ if(op[0]==‘=‘){ for(int i = 1; i <= c; i++){ ok(x,y,w); a[x][i].up = a[x][i].down = w; } } if(op[0]==‘>‘){ for(int i = 1; i <= c; i++){ a[x][i].down = max(a[x][i].down,w+1); } } if(op[0]==‘<‘){ for(int i = 1; i <= c; i++){ a[x][i].up = min(a[x][i].up,w-1); } } } } for(int i = 1; i <= r; i++){ for(int j = 1; j <= c; j++){ out[i]+=a[i][j].down; in[j+r]+=a[i][j].down; dinic.AddEdge(i,j+r,a[i][j].up-a[i][j].down); if(a[i][j].down>a[i][j].up){ flag = 1; } } } if(flag){ printf("IMPOSSIBLE\n"); continue; } dinic.AddEdge(t,s,INF); int ss = t+1, tt = t+2; if(in[s]>out[s]){ dinic.AddEdge(ss,s,in[s]-out[s]); } if(in[s]<out[s]){ dinic.AddEdge(s,tt,out[s]-in[s]); } if(in[t]>out[t]){ dinic.AddEdge(ss,t,in[t]-out[t]); } if(in[t]<out[t]){ dinic.AddEdge(t,tt,out[t]-in[t]); } for(int i = 1; i <= r+c; i++){ if(in[i]>out[i]){ dinic.AddEdge(ss,i,in[i]-out[i]); } if(in[i]<out[i]){ dinic.AddEdge(i,tt,out[i]-in[i]); } } dinic.Maxflow(ss,tt); dinic.print(r,c); } return 0; }
poj2396 Budget 有源汇上下界可行流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。