首页 > 代码库 > POJ2396_Budget
POJ2396_Budget
题意为给一个矩形数字阵,给出一些限制条件,包括每行和每列的和,还有一些位置的数值范围,求出满足情况的一个。
首先建图,源点->行和->列和->汇点,显然,行和列之间的边为那个数字的大小,只要我们能够找到一个满足大小条件的,且使的两边的和满流的流量方案就可以了。
由于存在下界(上界其实就是边的容量),根据图的特殊性,我们可以先在那边的相连的两条边都减去这个下界,这样就变成了一条只有上界的边了。
召唤代码君:
#include <iostream>#include <cstring>#include <cstdio>#define maxn 1022#define maxm 844442typedef long long ll;using namespace std;const ll inf=~0U>>1;ll to[maxm],next[maxm],c[maxm],first[maxn],edge;ll fmin[maxn][maxn],fmax[maxn][maxn],sr[maxn],sc[maxn];ll d[maxn],tag[maxn],TAG=222;ll Q[maxm],bot,top;ll ans[maxn][maxn];bool can[maxn];ll n,m,s,t,T,R,sumr,sumc;void _init(){ s=0,t=n+m+1,edge=-1,sumr=sumc=0; for (ll i=s; i<=t; i++) first[i]=-1; for (ll i=1; i<=n; i++) sr[i]=0; for (ll i=1; i<=m; i++) sc[i]=0; for (ll i=1; i<=n; i++) for (ll j=1; j<=m; j++) ans[i][j]=0,fmin[i][j]=0,fmax[i][j]=inf;}void minsize(ll x,ll y,ll dn,ll up){ fmin[x][y]=max(fmin[x][y],dn); fmax[x][y]=min(fmax[x][y],up);}bool check(){ for (ll i=1; i<=n; i++) for (ll j=1; j<=m; j++) { if (fmax[i][j]<0) return false; sr[i]-=fmin[i][j],sc[j]-=fmin[i][j]; sumr-=fmin[i][j],sumc-=fmin[i][j]; fmax[i][j]-=fmin[i][j]; if (fmax[i][j]<0 || sr[i]<0 || sc[j]<0) return false; } return sumr==sumc;}void addedge(ll U,ll V,ll W){ edge++; to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge; edge++; to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}bool bfs(){ Q[bot=top=1]=t,tag[t]=++TAG,d[t]=0,can[t]=false; while (bot<=top) { ll cur=Q[bot++]; for (ll i=first[cur]; i!=-1; i=next[i]) if (c[i^1] && tag[to[i]]!=TAG) { tag[to[i]]=TAG,d[to[i]]=d[cur]+1; can[to[i]]=false,Q[++top]=to[i]; if (to[i]==s) return true; } } return false;}ll dfs(ll cur,ll num){ if (cur==t) return num; ll tmp=num,k; for (ll i=first[cur]; i!=-1; i=next[i]) if (c[i] && d[to[i]]==d[cur]-1 && tag[to[i]]==TAG && !can[to[i]]) { k=dfs(to[i],min(c[i],num)); if (k) num-=k,c[i]-=k,c[i^1]+=k; if (!num) break; } if (num) can[cur]=true; return tmp-num;}ll maxflow(){ ll tot=0; while (bfs()) tot+=dfs(s,~0U>>1); return tot;}int main(){ char S[3]; ll x,y,z,cas=0,up,dn; scanf("%I64d",&T); while (T--) { scanf("%I64d%I64d",&n,&m); _init(); for (ll i=1; i<=n; i++) scanf("%I64d",&sr[i]),sumr+=sr[i]; for (ll i=1; i<=m; i++) scanf("%I64d",&sc[i]),sumc+=sc[i]; scanf("%I64d",&R); while (R--) { scanf("%I64d%I64d%s%I64d",&x,&y,S,&z); if (S[0]==‘=‘) up=z,dn=max(0LL,z); else if (S[0]==‘>‘) up=inf,dn=max(0LL,z+1); else up=z-1,dn=0; if (x==0 && y==0) { for (ll i=1; i<=n; i++) for (ll j=1; j<=m; j++) minsize(i,j,dn,up); } else if (x==0) { for (ll i=1; i<=n; i++) minsize(i,y,dn,up); } else if (y==0) { for (ll j=1; j<=m; j++) minsize(x,j,dn,up); } else minsize(x,y,dn,up); } if (cas++) puts(""); if (!check()) { puts("IMPOSSIBLE"); continue; } for (ll i=1; i<=n; i++) addedge(s,i,sr[i]); for (ll j=1; j<=m; j++) addedge(n+j,t,sc[j]); for (ll i=1; i<=n; i++) for (ll j=1; j<=m; j++) if (fmax[i][j]>0) addedge(i,n+j,fmax[i][j]); /* for (int i=1; i<=n; i++) { cout<<" hehe : "; for (int j=1; j<=m; j++) cout<<fmin[i][j]<<"("<<fmax[i][j]<<") ... "; cout<<endl; } */ if (maxflow()!=sumr) { puts("IMPOSSIBLE"); continue; } for (ll i=n+n+m+m; i<=edge; i+=2) { x=to[i+1],y=to[i]-n; ans[x][y]=c[i+1]; } for (ll i=1; i<=n; i++) { printf("%I64d",ans[i][1]+fmin[i][1]); for (ll j=2; j<=m; j++) printf(" %I64d",ans[i][j]+fmin[i][j]); printf("\n"); } } return 0;}
POJ2396_Budget
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。