首页 > 代码库 > POJ2396&ZOJ1994--Budget【有源汇上下界可行流】
POJ2396&ZOJ1994--Budget【有源汇上下界可行流】
链接:http://poj.org/problem?id=2396
题意:给一个n*m的矩阵,给出每行的总和以及每列的总和,再给出某些位置的最小或最大限制,问是否存在可能的矩阵,如果存在输出一种矩阵信息。
思路:这是一个有源汇的上下界可行流,对于这种题,从汇点连一条弧到源点,容量为INF,这不会影响流量平衡条件,并且此时原图转换为了无源汇的上下界可行流,剩下的做法和无源汇一样。
建图:原图源点src连向每个行顶点,容量为每行的和,每个列顶点连向汇点,容量为每个列顶点的和,行顶点和列顶点间也各有一条弧,初始容量无下界、无上界,输入时再更新。最后连一条汇点指向源点的容量为INF的弧,剩下就是无源汇的做法。
这道题细节还是挺多的,初始化挫了WA出了翔。还有我在POJ上C++交TLE了,去ZOJ上交却过了,再回POJ用G++交才AC,不明觉厉。
isap代码
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 100100 #define eps 1e-7 #define INF 0x7FFFFFFF #define seed 131 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson r,m+1,rt<<1|1 struct node{ int u,v,w,next; }edge[20000]; int head[250],dist[250],cur[250],fa[250],num[250]; int low[300][300],upp[300][300],D[250]; int n,m,cnt,nn,src,sink,supersrc,supersink; void add_edge(int a,int b,int c){ edge[cnt].u = a; edge[cnt].v = b; edge[cnt].w = c; edge[cnt].next = head[a]; head[a] = cnt++; } void build_graph(){ int i,j; for(i=1;i<=n;i++){ for(j=n+1;j<=n+m;j++){ D[i] -= low[i][j]; D[j] += low[i][j]; add_edge(i,j,upp[i][j]-low[i][j]); add_edge(j,i,0); } } add_edge(sink,src,INF); add_edge(src,sink,0); for(i=0;i<=n+m+1;i++){ if(D[i]==0) continue; else if(D[i]>0){ add_edge(supersrc,i,D[i]); add_edge(i,supersrc,0); } else{ add_edge(i,supersink,-D[i]); add_edge(supersink,i,0); } } } void bfs() { int x,i,j; queue<int> q; memset(dist,-1,sizeof(dist)); q.push(supersink); dist[supersink] = 0; while(!q.empty()){ x = q.front(); q.pop(); for(i=head[x];i!=-1;i=edge[i].next){ if(dist[edge[i].v]<0){ dist[edge[i].v] = dist[x] + 1; q.push(edge[i].v); } } } } int augment() { int x=supersink,a=INF; while(x!=supersrc){ a = min(a,edge[fa[x]].w); x = edge[fa[x]].u; } x=supersink; while(x!=supersrc){ edge[fa[x]].w -= a; edge[fa[x]^1].w += a; x = edge[fa[x]].u; } return a; } int isap() { int i,x,ok,minm,flow=0; memset(num,0,sizeof(num)); bfs(); for(i=0;i<=nn+1;i++) num[dist[i]]++; for(i=0;i<=nn+1;i++) cur[i] = head[i]; x=supersrc; while(dist[supersrc]<nn){ if(x==supersink){ flow += augment(); x = supersrc; } ok=0; for(i=cur[x];i!=-1;i=edge[i].next){ if(edge[i].w && dist[x]==dist[edge[i].v]+1){ ok=1; fa[edge[i].v] = i; cur[x] = i; x = edge[i].v; break; } } if(!ok){ minm = nn - 1; for(i=head[x];i!=-1;i=edge[i].next) if(edge[i].w && dist[edge[i].v]<minm) minm=dist[edge[i].v]; if(--num[dist[x]]==0)break; num[dist[x]=minm+1]++; cur[x]=head[x]; if(x!=supersrc) x=edge[fa[x]].u; } } return flow; } int main(){ int t,q,i,j; int a,b,c,d; char str[5]; scanf("%d",&t); int cas = 0; while(t--){ if(!cas) cas = 1; else puts(""); scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); memset(D,0,sizeof(D)); cnt = 0; src = http://www.mamicode.com/0;>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。