POJ2396_Budget

题意为给一个矩形数字阵,给出一些限制条件,包括每行和每列的和,还有一些位置的数值范围,求出满足情况的一个。

首先建图,源点->行和->列和->汇点,显然,行和列之间的边为那个数字的大小,只要我们能够找到一个满足大小条件的,且使的两边的和满流的流量方案就可以了。

由于存在下界(上界其实就是边的容量),根据图的特殊性,我们可以先在那边的相连的两条边都减去这个下界,这样就变成了一条只有上界的边了。

召唤代码君:

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 1022
#define maxm 844442
typedef long long ll;
using namespace std; const ll inf=~0U>>;
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=;
ll Q[maxm],bot,top;
ll ans[maxn][maxn];
bool can[maxn];
ll n,m,s,t,T,R,sumr,sumc; void _init()
{
s=,t=n+m+,edge=-,sumr=sumc=;
for (ll i=s; i<=t; i++) first[i]=-;
for (ll i=; i<=n; i++) sr[i]=;
for (ll i=; i<=m; i++) sc[i]=;
for (ll i=; i<=n; i++)
for (ll j=; j<=m; j++) ans[i][j]=,fmin[i][j]=,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=; i<=n; i++)
for (ll j=; j<=m; j++)
{
if (fmax[i][j]<) 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]< || sr[i]< || sc[j]<) 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]=,next[edge]=first[V],first[V]=edge;
} bool bfs()
{
Q[bot=top=]=t,tag[t]=++TAG,d[t]=,can[t]=false;
while (bot<=top)
{
ll cur=Q[bot++];
for (ll i=first[cur]; i!=-; i=next[i])
if (c[i^] && tag[to[i]]!=TAG)
{
tag[to[i]]=TAG,d[to[i]]=d[cur]+;
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!=-; i=next[i])
if (c[i] && d[to[i]]==d[cur]- && tag[to[i]]==TAG && !can[to[i]])
{
k=dfs(to[i],min(c[i],num));
if (k) num-=k,c[i]-=k,c[i^]+=k;
if (!num) break;
}
if (num) can[cur]=true;
return tmp-num;
} ll maxflow()
{
ll tot=;
while (bfs()) tot+=dfs(s,~0U>>);
return tot;
} int main()
{
char S[];
ll x,y,z,cas=,up,dn;
scanf("%I64d",&T);
while (T--)
{
scanf("%I64d%I64d",&n,&m);
_init();
for (ll i=; i<=n; i++) scanf("%I64d",&sr[i]),sumr+=sr[i];
for (ll i=; 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[]=='=') up=z,dn=max(0LL,z);
else if (S[]=='>') up=inf,dn=max(0LL,z+);
else up=z-,dn=;
if (x== && y==)
{
for (ll i=; i<=n; i++)
for (ll j=; j<=m; j++) minsize(i,j,dn,up);
}
else if (x==)
{
for (ll i=; i<=n; i++) minsize(i,y,dn,up);
}
else if (y==)
{
for (ll j=; 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=; i<=n; i++) addedge(s,i,sr[i]);
for (ll j=; j<=m; j++) addedge(n+j,t,sc[j]);
for (ll i=; i<=n; i++)
for (ll j=; j<=m; j++)
if (fmax[i][j]>) 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+=)
{
x=to[i+],y=to[i]-n;
ans[x][y]=c[i+];
}
for (ll i=; i<=n; i++)
{
printf("%I64d",ans[i][]+fmin[i][]);
for (ll j=; j<=m; j++) printf(" %I64d",ans[i][j]+fmin[i][j]);
printf("\n");
}
}
return ;
}
上一篇:JIRA官方:JIRA亮点介绍


下一篇:Linux源码编译安装nginx