首页 > 代码库 > 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